Bucketsort (German Wikipedia)

Analysis of information sources in references of the Wikipedia article "Bucketsort" in German language version.

refsWebsite

Global rank German rank

2^nd place

3^rd place

doi.org

s. #Mehlhorn.
Aber auch eine erschöpfende Rechnung

$n$	Partitio- nenzahl	$\emptyset$ Anzahl Vergleiche	$\emptyset /n$
2	2	0,5000	0,25000
3	3	0,9630	0,32099
4	5	1,4167	0,35417
5	7	1,8675	0,37349
6	11	2,3169	0,38616
7	15	2,7657	0,39510
8	22	3,2140	0,40175
9	30	3,6620	0,40689
10	42	4,1098	0,41098
11	56	4,5575	0,41432
12	77	5,0051	0,41709
13	101	5,4526	0,41943
14	135	5,9000	0,42143
15	176	6,3474	0,42316
16	231	6,7947	0,42467
17	297	7,2420	0,42600
18	385	7,6893	0,42718
19	490	8,1366	0,42824
20	627	8,5838	0,42919
21	792	9,0310	0,43005
22	1002	9,4782	0,43083
23	1255	9,9254	0,43154
24	1575	10,373	0,43219
25	1958	10,820	0,43279
26	2436	11,267	0,43334
27	3010	11,714	0,43386
28	3718	12,161	0,43433
29	4565	12,608	0,43477
30	5604	13,056	0,43518
31	6842	13,503	0,43557
32	8349	13,950	0,43593
33	10143	14,397	0,43627

über alle Permutationen zeigt, dass bis zu einer Elementeanzahl von $n\leq 33$ im Mittel weniger als $n/2$ Vergleiche zum vollständigen Sortieren erforderlich sind.

Kurt Mehlhorn, Peter Sanders: Algorithms and Data Structures. The Basic Toolbox. Springer, Berlin / Heidelberg 2008, ISBN 978-3-540-77977-3, doi:10.1007/978-3-540-77978-0. 5.6 Breaking the Lower Bound