Mercurial > cpython-lru_cache-weakref

annotate Objects/listsort.txt @ 54294:dba767bc3155 legacy-trunk

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
remove mention of old ctypes version
author Benjamin Peterson <benjamin@python.org>
date Sat, 23 May 2009 20:59:09 +0000
parents 74c0a78114ae
children 1ea833ecaf5a afbb2b2ff6f7
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
24455
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
1 Intro
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
2 -----
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
3 This describes an adaptive, stable, natural mergesort, modestly called
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
4 timsort (hey, I earned it <wink>). It has supernatural performance on many
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
5 kinds of partially ordered arrays (less than lg(N!) comparisons needed, and
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
6 as few as N-1), yet as fast as Python's previous highly tuned samplesort
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
7 hybrid on random arrays.
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
8
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
9 In a nutshell, the main routine marches over the array once, left to right,
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
10 alternately identifying the next run, then merging it into the previous
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
11 runs "intelligently". Everything else is complication for speed, and some
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
12 hard-won measure of memory efficiency.
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
13
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
14
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
15 Comparison with Python's Samplesort Hybrid
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
16 ------------------------------------------
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
17 + timsort can require a temp array containing as many as N//2 pointers,
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
18 which means as many as 2*N extra bytes on 32-bit boxes. It can be
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
19 expected to require a temp array this large when sorting random data; on
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
20 data with significant structure, it may get away without using any extra
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
21 heap memory. This appears to be the strongest argument against it, but
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
22 compared to the size of an object, 2 temp bytes worst-case (also expected-
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
23 case for random data) doesn't scare me much.
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
24
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
25 It turns out that Perl is moving to a stable mergesort, and the code for
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
26 that appears always to require a temp array with room for at least N
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
27 pointers. (Note that I wouldn't want to do that even if space weren't an
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
28 issue; I believe its efforts at memory frugality also save timsort
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
29 significant pointer-copying costs, and allow it to have a smaller working
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
30 set.)
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
31
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
32 + Across about four hours of generating random arrays, and sorting them
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
33 under both methods, samplesort required about 1.5% more comparisons
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
34 (the program is at the end of this file).
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
35
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
36 + In real life, this may be faster or slower on random arrays than
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
37 samplesort was, depending on platform quirks. Since it does fewer
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
38 comparisons on average, it can be expected to do better the more
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
39 expensive a comparison function is. OTOH, it does more data movement
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
40 (pointer copying) than samplesort, and that may negate its small
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
41 comparison advantage (depending on platform quirks) unless comparison
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
42 is very expensive.
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
43
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
44 + On arrays with many kinds of pre-existing order, this blows samplesort out
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
45 of the water. It's significantly faster than samplesort even on some
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
46 cases samplesort was special-casing the snot out of. I believe that lists
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
47 very often do have exploitable partial order in real life, and this is the
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
48 strongest argument in favor of timsort (indeed, samplesort's special cases
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
49 for extreme partial order are appreciated by real users, and timsort goes
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
50 much deeper than those, in particular naturally covering every case where
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
51 someone has suggested "and it would be cool if list.sort() had a special
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
52 case for this too ... and for that ...").
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
53
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
54 + Here are exact comparison counts across all the tests in sortperf.py,
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
55 when run with arguments "15 20 1".
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
56
35632
03cfdcbc4d1f The key to the various sort columns got lost. Pulled from
Skip Montanaro <skip@pobox.com>
parents: 24730
diff changeset
57 Column Key:
03cfdcbc4d1f The key to the various sort columns got lost. Pulled from
Skip Montanaro <skip@pobox.com>
parents: 24730
diff changeset
58 *sort: random data
03cfdcbc4d1f The key to the various sort columns got lost. Pulled from
Skip Montanaro <skip@pobox.com>
parents: 24730
diff changeset
59 \sort: descending data
03cfdcbc4d1f The key to the various sort columns got lost. Pulled from
Skip Montanaro <skip@pobox.com>
parents: 24730
diff changeset
60 /sort: ascending data
03cfdcbc4d1f The key to the various sort columns got lost. Pulled from
Skip Montanaro <skip@pobox.com>
parents: 24730
diff changeset
61 3sort: ascending, then 3 random exchanges
03cfdcbc4d1f The key to the various sort columns got lost. Pulled from
Skip Montanaro <skip@pobox.com>
parents: 24730
diff changeset
62 +sort: ascending, then 10 random at the end
03cfdcbc4d1f The key to the various sort columns got lost. Pulled from
Skip Montanaro <skip@pobox.com>
parents: 24730
diff changeset
63 ~sort: many duplicates
03cfdcbc4d1f The key to the various sort columns got lost. Pulled from
Skip Montanaro <skip@pobox.com>
parents: 24730
diff changeset
64 =sort: all equal
03cfdcbc4d1f The key to the various sort columns got lost. Pulled from
Skip Montanaro <skip@pobox.com>
parents: 24730
diff changeset
65 !sort: worst case scenario
03cfdcbc4d1f The key to the various sort columns got lost. Pulled from
Skip Montanaro <skip@pobox.com>
parents: 24730
diff changeset
66
24455
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
67 First the trivial cases, trivial for samplesort because it special-cased
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
68 them, and trivial for timsort because it naturally works on runs. Within
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
69 an "n" block, the first line gives the # of compares done by samplesort,
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
70 the second line by timsort, and the third line is the percentage by
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
71 which the samplesort count exceeds the timsort count:
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
72
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
73 n \sort /sort =sort
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
74 ------- ------ ------ ------
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
75 32768 32768 32767 32767 samplesort
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
76 32767 32767 32767 timsort
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
77 0.00% 0.00% 0.00% (samplesort - timsort) / timsort
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
78
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
79 65536 65536 65535 65535
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
80 65535 65535 65535
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
81 0.00% 0.00% 0.00%
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
82
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
83 131072 131072 131071 131071
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
84 131071 131071 131071
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
85 0.00% 0.00% 0.00%
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
86
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
87 262144 262144 262143 262143
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
88 262143 262143 262143
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
89 0.00% 0.00% 0.00%
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
90
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
91 524288 524288 524287 524287
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
92 524287 524287 524287
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
93 0.00% 0.00% 0.00%
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
94
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
95 1048576 1048576 1048575 1048575
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
96 1048575 1048575 1048575
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
97 0.00% 0.00% 0.00%
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
98
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
99 The algorithms are effectively identical in these cases, except that
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
100 timsort does one less compare in \sort.
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
101
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
102 Now for the more interesting cases. lg(n!) is the information-theoretic
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
103 limit for the best any comparison-based sorting algorithm can do on
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
104 average (across all permutations). When a method gets significantly
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
105 below that, it's either astronomically lucky, or is finding exploitable
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
106 structure in the data.
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
107
24727
b5640e74aa5c 1. Combined the base and length arrays into a single array of structs.
Tim Peters <tim.peters@gmail.com>
parents: 24726
diff changeset
108 n lg(n!) *sort 3sort +sort %sort ~sort !sort
b5640e74aa5c 1. Combined the base and length arrays into a single array of structs.
Tim Peters <tim.peters@gmail.com>
parents: 24726
diff changeset
109 ------- ------- ------ ------- ------- ------ ------- --------
b5640e74aa5c 1. Combined the base and length arrays into a single array of structs.
Tim Peters <tim.peters@gmail.com>
parents: 24726
diff changeset
110 32768 444255 453096 453614 32908 452871 130491 469141 old
b5640e74aa5c 1. Combined the base and length arrays into a single array of structs.
Tim Peters <tim.peters@gmail.com>
parents: 24726
diff changeset
111 448885 33016 33007 50426 182083 65534 new
b5640e74aa5c 1. Combined the base and length arrays into a single array of structs.
Tim Peters <tim.peters@gmail.com>
parents: 24726
diff changeset
112 0.94% 1273.92% -0.30% 798.09% -28.33% 615.87% %ch from new
24455
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
113
24726
bbd5f8af588a The samplesort-vs-mergesort #-of-comparisons comparisons were captured
Tim Peters <tim.peters@gmail.com>
parents: 24689
diff changeset
114 65536 954037 972699 981940 65686 973104 260029 1004607
24727
b5640e74aa5c 1. Combined the base and length arrays into a single array of structs.
Tim Peters <tim.peters@gmail.com>
parents: 24726
diff changeset
115 962991 65821 65808 101667 364341 131070
b5640e74aa5c 1. Combined the base and length arrays into a single array of structs.
Tim Peters <tim.peters@gmail.com>
parents: 24726
diff changeset
116 1.01% 1391.83% -0.19% 857.15% -28.63% 666.47%
24455
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
117
24726
bbd5f8af588a The samplesort-vs-mergesort #-of-comparisons comparisons were captured
Tim Peters <tim.peters@gmail.com>
parents: 24689
diff changeset
118 131072 2039137 2101881 2091491 131232 2092894 554790 2161379
24727
b5640e74aa5c 1. Combined the base and length arrays into a single array of structs.
Tim Peters <tim.peters@gmail.com>
parents: 24726
diff changeset
119 2057533 131410 131361 206193 728871 262142
b5640e74aa5c 1. Combined the base and length arrays into a single array of structs.
Tim Peters <tim.peters@gmail.com>
parents: 24726
diff changeset
120 2.16% 1491.58% -0.10% 915.02% -23.88% 724.51%
24455
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
121
24726
bbd5f8af588a The samplesort-vs-mergesort #-of-comparisons comparisons were captured
Tim Peters <tim.peters@gmail.com>
parents: 24689
diff changeset
122 262144 4340409 4464460 4403233 262314 4445884 1107842 4584560
24727
b5640e74aa5c 1. Combined the base and length arrays into a single array of structs.
Tim Peters <tim.peters@gmail.com>
parents: 24726
diff changeset
123 4377402 262437 262459 416347 1457945 524286
b5640e74aa5c 1. Combined the base and length arrays into a single array of structs.
Tim Peters <tim.peters@gmail.com>
parents: 24726
diff changeset
124 1.99% 1577.82% -0.06% 967.83% -24.01% 774.44%
24455
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
125
24730
8d850d58f109 Fixed new typos, added a little info about ~sort versus "hint"s.
Tim Peters <tim.peters@gmail.com>
parents: 24727
diff changeset
126 524288 9205096 9453356 9408463 524468 9441930 2218577 9692015
8d850d58f109 Fixed new typos, added a little info about ~sort versus "hint"s.
Tim Peters <tim.peters@gmail.com>
parents: 24727
diff changeset
127 9278734 524580 524633 837947 2916107 1048574
24727
b5640e74aa5c 1. Combined the base and length arrays into a single array of structs.
Tim Peters <tim.peters@gmail.com>
parents: 24726
diff changeset
128 1.88% 1693.52% -0.03% 1026.79% -23.92% 824.30%
24455
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
129
24726
bbd5f8af588a The samplesort-vs-mergesort #-of-comparisons comparisons were captured
Tim Peters <tim.peters@gmail.com>
parents: 24689
diff changeset
130 1048576 19458756 19950272 19838588 1048766 19912134 4430649 20434212
24727
b5640e74aa5c 1. Combined the base and length arrays into a single array of structs.
Tim Peters <tim.peters@gmail.com>
parents: 24726
diff changeset
131 19606028 1048958 1048941 1694896 5832445 2097150
b5640e74aa5c 1. Combined the base and length arrays into a single array of structs.
Tim Peters <tim.peters@gmail.com>
parents: 24726
diff changeset
132 1.76% 1791.27% -0.02% 1074.83% -24.03% 874.38%
24455
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
133
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
134 Discussion of cases:
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
135
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
136 *sort: There's no structure in random data to exploit, so the theoretical
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
137 limit is lg(n!). Both methods get close to that, and timsort is hugging
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
138 it (indeed, in a *marginal* sense, it's a spectacular improvement --
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
139 there's only about 1% left before hitting the wall, and timsort knows
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
140 darned well it's doing compares that won't pay on random data -- but so
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
141 does the samplesort hybrid). For contrast, Hoare's original random-pivot
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
142 quicksort does about 39% more compares than the limit, and the median-of-3
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
143 variant about 19% more.
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
144
24726
bbd5f8af588a The samplesort-vs-mergesort #-of-comparisons comparisons were captured
Tim Peters <tim.peters@gmail.com>
parents: 24689
diff changeset
145 3sort, %sort, and !sort: No contest; there's structure in this data, but
bbd5f8af588a The samplesort-vs-mergesort #-of-comparisons comparisons were captured
Tim Peters <tim.peters@gmail.com>
parents: 24689
diff changeset
146 not of the specific kinds samplesort special-cases. Note that structure
bbd5f8af588a The samplesort-vs-mergesort #-of-comparisons comparisons were captured
Tim Peters <tim.peters@gmail.com>
parents: 24689
diff changeset
147 in !sort wasn't put there on purpose -- it was crafted as a worst case for
bbd5f8af588a The samplesort-vs-mergesort #-of-comparisons comparisons were captured
Tim Peters <tim.peters@gmail.com>
parents: 24689
diff changeset
148 a previous quicksort implementation. That timsort nails it came as a
24455
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
149 surprise to me (although it's obvious in retrospect).
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
150
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
151 +sort: samplesort special-cases this data, and does a few less compares
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
152 than timsort. However, timsort runs this case significantly faster on all
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
153 boxes we have timings for, because timsort is in the business of merging
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
154 runs efficiently, while samplesort does much more data movement in this
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
155 (for it) special case.
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
156
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
157 ~sort: samplesort's special cases for large masses of equal elements are
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
158 extremely effective on ~sort's specific data pattern, and timsort just
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
159 isn't going to get close to that, despite that it's clearly getting a
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
160 great deal of benefit out of the duplicates (the # of compares is much less
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
161 than lg(n!)). ~sort has a perfectly uniform distribution of just 4
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
162 distinct values, and as the distribution gets more skewed, samplesort's
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
163 equal-element gimmicks become less effective, while timsort's adaptive
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
164 strategies find more to exploit; in a database supplied by Kevin Altis, a
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
165 sort on its highly skewed "on which stock exchange does this company's
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
166 stock trade?" field ran over twice as fast under timsort.
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
167
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
168 However, despite that timsort does many more comparisons on ~sort, and
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
169 that on several platforms ~sort runs highly significantly slower under
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
170 timsort, on other platforms ~sort runs highly significantly faster under
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
171 timsort. No other kind of data has shown this wild x-platform behavior,
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
172 and we don't have an explanation for it. The only thing I can think of
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
173 that could transform what "should be" highly significant slowdowns into
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
174 highly significant speedups on some boxes are catastrophic cache effects
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
175 in samplesort.
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
176
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
177 But timsort "should be" slower than samplesort on ~sort, so it's hard
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
178 to count that it isn't on some boxes as a strike against it <wink>.
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
179
24658
8bc265b084d9 Added info about highwater heap-memory use for the sortperf.py tests; + a
Tim Peters <tim.peters@gmail.com>
parents: 24455
diff changeset
180 + Here's the highwater mark for the number of heap-based temp slots (4
8bc265b084d9 Added info about highwater heap-memory use for the sortperf.py tests; + a
Tim Peters <tim.peters@gmail.com>
parents: 24455
diff changeset
181 bytes each on this box) needed by each test, again with arguments
8bc265b084d9 Added info about highwater heap-memory use for the sortperf.py tests; + a
Tim Peters <tim.peters@gmail.com>
parents: 24455
diff changeset
182 "15 20 1":
8bc265b084d9 Added info about highwater heap-memory use for the sortperf.py tests; + a
Tim Peters <tim.peters@gmail.com>
parents: 24455
diff changeset
183
8bc265b084d9 Added info about highwater heap-memory use for the sortperf.py tests; + a
Tim Peters <tim.peters@gmail.com>
parents: 24455
diff changeset
184 2**i *sort \sort /sort 3sort +sort %sort ~sort =sort !sort
8bc265b084d9 Added info about highwater heap-memory use for the sortperf.py tests; + a
Tim Peters <tim.peters@gmail.com>
parents: 24455
diff changeset
185 32768 16384 0 0 6256 0 10821 12288 0 16383
8bc265b084d9 Added info about highwater heap-memory use for the sortperf.py tests; + a
Tim Peters <tim.peters@gmail.com>
parents: 24455
diff changeset
186 65536 32766 0 0 21652 0 31276 24576 0 32767
8bc265b084d9 Added info about highwater heap-memory use for the sortperf.py tests; + a
Tim Peters <tim.peters@gmail.com>
parents: 24455
diff changeset
187 131072 65534 0 0 17258 0 58112 49152 0 65535
8bc265b084d9 Added info about highwater heap-memory use for the sortperf.py tests; + a
Tim Peters <tim.peters@gmail.com>
parents: 24455
diff changeset
188 262144 131072 0 0 35660 0 123561 98304 0 131071
8bc265b084d9 Added info about highwater heap-memory use for the sortperf.py tests; + a
Tim Peters <tim.peters@gmail.com>
parents: 24455
diff changeset
189 524288 262142 0 0 31302 0 212057 196608 0 262143
8bc265b084d9 Added info about highwater heap-memory use for the sortperf.py tests; + a
Tim Peters <tim.peters@gmail.com>
parents: 24455
diff changeset
190 1048576 524286 0 0 312438 0 484942 393216 0 524287
8bc265b084d9 Added info about highwater heap-memory use for the sortperf.py tests; + a
Tim Peters <tim.peters@gmail.com>
parents: 24455
diff changeset
191
8bc265b084d9 Added info about highwater heap-memory use for the sortperf.py tests; + a
Tim Peters <tim.peters@gmail.com>
parents: 24455
diff changeset
192 Discussion: The tests that end up doing (close to) perfectly balanced
8bc265b084d9 Added info about highwater heap-memory use for the sortperf.py tests; + a
Tim Peters <tim.peters@gmail.com>
parents: 24455
diff changeset
193 merges (*sort, !sort) need all N//2 temp slots (or almost all). ~sort
8bc265b084d9 Added info about highwater heap-memory use for the sortperf.py tests; + a
Tim Peters <tim.peters@gmail.com>
parents: 24455
diff changeset
194 also ends up doing balanced merges, but systematically benefits a lot from
8bc265b084d9 Added info about highwater heap-memory use for the sortperf.py tests; + a
Tim Peters <tim.peters@gmail.com>
parents: 24455
diff changeset
195 the preliminary pre-merge searches described under "Merge Memory" later.
8bc265b084d9 Added info about highwater heap-memory use for the sortperf.py tests; + a
Tim Peters <tim.peters@gmail.com>
parents: 24455
diff changeset
196 %sort approaches having a balanced merge at the end because the random
8bc265b084d9 Added info about highwater heap-memory use for the sortperf.py tests; + a
Tim Peters <tim.peters@gmail.com>
parents: 24455
diff changeset
197 selection of elements to replace is expected to produce an out-of-order
8bc265b084d9 Added info about highwater heap-memory use for the sortperf.py tests; + a
Tim Peters <tim.peters@gmail.com>
parents: 24455
diff changeset
198 element near the midpoint. \sort, /sort, =sort are the trivial one-run
8bc265b084d9 Added info about highwater heap-memory use for the sortperf.py tests; + a
Tim Peters <tim.peters@gmail.com>
parents: 24455
diff changeset
199 cases, needing no merging at all. +sort ends up having one very long run
8bc265b084d9 Added info about highwater heap-memory use for the sortperf.py tests; + a
Tim Peters <tim.peters@gmail.com>
parents: 24455
diff changeset
200 and one very short, and so gets all the temp space it needs from the small
8bc265b084d9 Added info about highwater heap-memory use for the sortperf.py tests; + a
Tim Peters <tim.peters@gmail.com>
parents: 24455
diff changeset
201 temparray member of the MergeState struct (note that the same would be
8bc265b084d9 Added info about highwater heap-memory use for the sortperf.py tests; + a
Tim Peters <tim.peters@gmail.com>
parents: 24455
diff changeset
202 true if the new random elements were prefixed to the sorted list instead,
8bc265b084d9 Added info about highwater heap-memory use for the sortperf.py tests; + a
Tim Peters <tim.peters@gmail.com>
parents: 24455
diff changeset
203 but not if they appeared "in the middle"). 3sort approaches N//3 temp
8bc265b084d9 Added info about highwater heap-memory use for the sortperf.py tests; + a
Tim Peters <tim.peters@gmail.com>
parents: 24455
diff changeset
204 slots twice, but the run lengths that remain after 3 random exchanges
8bc265b084d9 Added info about highwater heap-memory use for the sortperf.py tests; + a
Tim Peters <tim.peters@gmail.com>
parents: 24455
diff changeset
205 clearly has very high variance.
8bc265b084d9 Added info about highwater heap-memory use for the sortperf.py tests; + a
Tim Peters <tim.peters@gmail.com>
parents: 24455
diff changeset
206
24455
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
207
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
208 A detailed description of timsort follows.
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
209
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
210 Runs
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
211 ----
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
212 count_run() returns the # of elements in the next run. A run is either
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
213 "ascending", which means non-decreasing:
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
214
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
215 a0 <= a1 <= a2 <= ...
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
216
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
217 or "descending", which means strictly decreasing:
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
218
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
219 a0 > a1 > a2 > ...
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
220
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
221 Note that a run is always at least 2 long, unless we start at the array's
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
222 last element.
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
223
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
224 The definition of descending is strict, because the main routine reverses
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
225 a descending run in-place, transforming a descending run into an ascending
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
226 run. Reversal is done via the obvious fast "swap elements starting at each
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
227 end, and converge at the middle" method, and that can violate stability if
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
228 the slice contains any equal elements. Using a strict definition of
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
229 descending ensures that a descending run contains distinct elements.
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
230
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
231 If an array is random, it's very unlikely we'll see long runs. If a natural
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
232 run contains less than minrun elements (see next section), the main loop
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
233 artificially boosts it to minrun elements, via a stable binary insertion sort
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
234 applied to the right number of array elements following the short natural
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
235 run. In a random array, *all* runs are likely to be minrun long as a
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
236 result. This has two primary good effects:
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
237
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
238 1. Random data strongly tends then toward perfectly balanced (both runs have
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
239 the same length) merges, which is the most efficient way to proceed when
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
240 data is random.
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
241
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
242 2. Because runs are never very short, the rest of the code doesn't make
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
243 heroic efforts to shave a few cycles off per-merge overheads. For
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
244 example, reasonable use of function calls is made, rather than trying to
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
245 inline everything. Since there are no more than N/minrun runs to begin
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
246 with, a few "extra" function calls per merge is barely measurable.
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
247
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
248
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
249 Computing minrun
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
250 ----------------
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
251 If N < 64, minrun is N. IOW, binary insertion sort is used for the whole
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
252 array then; it's hard to beat that given the overheads of trying something
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
253 fancier.
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
254
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
255 When N is a power of 2, testing on random data showed that minrun values of
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
256 16, 32, 64 and 128 worked about equally well. At 256 the data-movement cost
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
257 in binary insertion sort clearly hurt, and at 8 the increase in the number
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
258 of function calls clearly hurt. Picking *some* power of 2 is important
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
259 here, so that the merges end up perfectly balanced (see next section). We
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
260 pick 32 as a good value in the sweet range; picking a value at the low end
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
261 allows the adaptive gimmicks more opportunity to exploit shorter natural
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
262 runs.
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
263
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
264 Because sortperf.py only tries powers of 2, it took a long time to notice
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
265 that 32 isn't a good choice for the general case! Consider N=2112:
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
266
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
267 >>> divmod(2112, 32)
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
268 (66, 0)
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
269 >>>
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
270
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
271 If the data is randomly ordered, we're very likely to end up with 66 runs
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
272 each of length 32. The first 64 of these trigger a sequence of perfectly
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
273 balanced merges (see next section), leaving runs of lengths 2048 and 64 to
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
274 merge at the end. The adaptive gimmicks can do that with fewer than 2048+64
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
275 compares, but it's still more compares than necessary, and-- mergesort's
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
276 bugaboo relative to samplesort --a lot more data movement (O(N) copies just
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
277 to get 64 elements into place).
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
278
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
279 If we take minrun=33 in this case, then we're very likely to end up with 64
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
280 runs each of length 33, and then all merges are perfectly balanced. Better!
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
281
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
282 What we want to avoid is picking minrun such that in
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
283
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
284 q, r = divmod(N, minrun)
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
285
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
286 q is a power of 2 and r>0 (then the last merge only gets r elements into
24689
debcf72067f0 Repaired a braino in the description of bad minrun values.
Tim Peters <tim.peters@gmail.com>
parents: 24658
diff changeset
287 place, and r < minrun is small compared to N), or q a little larger than a
debcf72067f0 Repaired a braino in the description of bad minrun values.
Tim Peters <tim.peters@gmail.com>
parents: 24658
diff changeset
288 power of 2 regardless of r (then we've got a case similar to "2112", again
debcf72067f0 Repaired a braino in the description of bad minrun values.
Tim Peters <tim.peters@gmail.com>
parents: 24658
diff changeset
289 leaving too little work for the last merge to do).
24455
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
290
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
291 Instead we pick a minrun in range(32, 65) such that N/minrun is exactly a
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
292 power of 2, or if that isn't possible, is close to, but strictly less than,
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
293 a power of 2. This is easier to do than it may sound: take the first 6
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
294 bits of N, and add 1 if any of the remaining bits are set. In fact, that
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
295 rule covers every case in this section, including small N and exact powers
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
296 of 2; merge_compute_minrun() is a deceptively simple function.
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
297
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
298
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
299 The Merge Pattern
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
300 -----------------
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
301 In order to exploit regularities in the data, we're merging on natural
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
302 run lengths, and they can become wildly unbalanced. That's a Good Thing
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
303 for this sort! It means we have to find a way to manage an assortment of
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
304 potentially very different run lengths, though.
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
305
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
306 Stability constrains permissible merging patterns. For example, if we have
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
307 3 consecutive runs of lengths
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
308
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
309 A:10000 B:20000 C:10000
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
310
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
311 we dare not merge A with C first, because if A, B and C happen to contain
55049
74c0a78114ae Merged revisions 69846 via svnmerge from
Jesus Cea <jcea@jcea.es>
parents: 39338
diff changeset
312 a common element, it would get out of order wrt its occurrence(s) in B. The
24455
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
313 merging must be done as (A+B)+C or A+(B+C) instead.
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
314
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
315 So merging is always done on two consecutive runs at a time, and in-place,
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
316 although this may require some temp memory (more on that later).
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
317
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
318 When a run is identified, its base address and length are pushed on a stack
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
319 in the MergeState struct. merge_collapse() is then called to see whether it
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
320 should merge it with preceding run(s). We would like to delay merging as
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
321 long as possible in order to exploit patterns that may come up later, but we
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
322 like even more to do merging as soon as possible to exploit that the run just
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
323 found is still high in the memory hierarchy. We also can't delay merging
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
324 "too long" because it consumes memory to remember the runs that are still
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
325 unmerged, and the stack has a fixed size.
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
326
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
327 What turned out to be a good compromise maintains two invariants on the
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
328 stack entries, where A, B and C are the lengths of the three righmost not-yet
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
329 merged slices:
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
330
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
331 1. A > B+C
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
332 2. B > C
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
333
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
334 Note that, by induction, #2 implies the lengths of pending runs form a
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
335 decreasing sequence. #1 implies that, reading the lengths right to left,
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
336 the pending-run lengths grow at least as fast as the Fibonacci numbers.
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
337 Therefore the stack can never grow larger than about log_base_phi(N) entries,
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
338 where phi = (1+sqrt(5))/2 ~= 1.618. Thus a small # of stack slots suffice
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
339 for very large arrays.
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
340
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
341 If A <= B+C, the smaller of A and C is merged with B (ties favor C, for the
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
342 freshness-in-cache reason), and the new run replaces the A,B or B,C entries;
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
343 e.g., if the last 3 entries are
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
344
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
345 A:30 B:20 C:10
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
346
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
347 then B is merged with C, leaving
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
348
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
349 A:30 BC:30
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
350
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
351 on the stack. Or if they were
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
352
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
353 A:500 B:400: C:1000
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
354
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
355 then A is merged with B, leaving
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
356
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
357 AB:900 C:1000
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
358
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
359 on the stack.
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
360
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
361 In both examples, the stack configuration after the merge still violates
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
362 invariant #2, and merge_collapse() goes on to continue merging runs until
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
363 both invariants are satisfied. As an extreme case, suppose we didn't do the
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
364 minrun gimmick, and natural runs were of lengths 128, 64, 32, 16, 8, 4, 2,
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
365 and 2. Nothing would get merged until the final 2 was seen, and that would
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
366 trigger 7 perfectly balanced merges.
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
367
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
368 The thrust of these rules when they trigger merging is to balance the run
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
369 lengths as closely as possible, while keeping a low bound on the number of
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
370 runs we have to remember. This is maximally effective for random data,
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
371 where all runs are likely to be of (artificially forced) length minrun, and
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
372 then we get a sequence of perfectly balanced merges (with, perhaps, some
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
373 oddballs at the end).
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
374
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
375 OTOH, one reason this sort is so good for partly ordered data has to do
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
376 with wildly unbalanced run lengths.
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
377
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
378
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
379 Merge Memory
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
380 ------------
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
381 Merging adjacent runs of lengths A and B in-place is very difficult.
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
382 Theoretical constructions are known that can do it, but they're too difficult
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
383 and slow for practical use. But if we have temp memory equal to min(A, B),
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
384 it's easy.
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
385
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
386 If A is smaller (function merge_lo), copy A to a temp array, leave B alone,
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
387 and then we can do the obvious merge algorithm left to right, from the temp
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
388 area and B, starting the stores into where A used to live. There's always a
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
389 free area in the original area comprising a number of elements equal to the
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
390 number not yet merged from the temp array (trivially true at the start;
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
391 proceed by induction). The only tricky bit is that if a comparison raises an
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
392 exception, we have to remember to copy the remaining elements back in from
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
393 the temp area, lest the array end up with duplicate entries from B. But
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
394 that's exactly the same thing we need to do if we reach the end of B first,
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
395 so the exit code is pleasantly common to both the normal and error cases.
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
396
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
397 If B is smaller (function merge_hi, which is merge_lo's "mirror image"),
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
398 much the same, except that we need to merge right to left, copying B into a
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
399 temp array and starting the stores at the right end of where B used to live.
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
400
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
401 A refinement: When we're about to merge adjacent runs A and B, we first do
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
402 a form of binary search (more on that later) to see where B[0] should end up
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
403 in A. Elements in A preceding that point are already in their final
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
404 positions, effectively shrinking the size of A. Likewise we also search to
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
405 see where A[-1] should end up in B, and elements of B after that point can
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
406 also be ignored. This cuts the amount of temp memory needed by the same
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
407 amount.
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
408
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
409 These preliminary searches may not pay off, and can be expected *not* to
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
410 repay their cost if the data is random. But they can win huge in all of
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
411 time, copying, and memory savings when they do pay, so this is one of the
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
412 "per-merge overheads" mentioned above that we're happy to endure because
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
413 there is at most one very short run. It's generally true in this algorithm
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
414 that we're willing to gamble a little to win a lot, even though the net
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
415 expectation is negative for random data.
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
416
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
417
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
418 Merge Algorithms
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
419 ----------------
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
420 merge_lo() and merge_hi() are where the bulk of the time is spent. merge_lo
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
421 deals with runs where A <= B, and merge_hi where A > B. They don't know
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
422 whether the data is clustered or uniform, but a lovely thing about merging
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
423 is that many kinds of clustering "reveal themselves" by how many times in a
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
424 row the winning merge element comes from the same run. We'll only discuss
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
425 merge_lo here; merge_hi is exactly analogous.
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
426
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
427 Merging begins in the usual, obvious way, comparing the first element of A
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
428 to the first of B, and moving B[0] to the merge area if it's less than A[0],
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
429 else moving A[0] to the merge area. Call that the "one pair at a time"
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
430 mode. The only twist here is keeping track of how many times in a row "the
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
431 winner" comes from the same run.
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
432
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
433 If that count reaches MIN_GALLOP, we switch to "galloping mode". Here
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
434 we *search* B for where A[0] belongs, and move over all the B's before
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
435 that point in one chunk to the merge area, then move A[0] to the merge
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
436 area. Then we search A for where B[0] belongs, and similarly move a
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
437 slice of A in one chunk. Then back to searching B for where A[0] belongs,
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
438 etc. We stay in galloping mode until both searches find slices to copy
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
439 less than MIN_GALLOP elements long, at which point we go back to one-pair-
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
440 at-a-time mode.
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
441
24727
b5640e74aa5c 1. Combined the base and length arrays into a single array of structs.
Tim Peters <tim.peters@gmail.com>
parents: 24726
diff changeset
442 A refinement: The MergeState struct contains the value of min_gallop that
b5640e74aa5c 1. Combined the base and length arrays into a single array of structs.
Tim Peters <tim.peters@gmail.com>
parents: 24726
diff changeset
443 controls when we enter galloping mode, initialized to MIN_GALLOP.
24730
8d850d58f109 Fixed new typos, added a little info about ~sort versus "hint"s.
Tim Peters <tim.peters@gmail.com>
parents: 24727
diff changeset
444 merge_lo() and merge_hi() adjust this higher when galloping isn't paying
24727
b5640e74aa5c 1. Combined the base and length arrays into a single array of structs.
Tim Peters <tim.peters@gmail.com>
parents: 24726
diff changeset
445 off, and lower when it is.
b5640e74aa5c 1. Combined the base and length arrays into a single array of structs.
Tim Peters <tim.peters@gmail.com>
parents: 24726
diff changeset
446
24455
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
447
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
448 Galloping
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
449 ---------
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
450 Still without loss of generality, assume A is the shorter run. In galloping
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
451 mode, we first look for A[0] in B. We do this via "galloping", comparing
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
452 A[0] in turn to B[0], B[1], B[3], B[7], ..., B[2**j - 1], ..., until finding
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
453 the k such that B[2**(k-1) - 1] < A[0] <= B[2**k - 1]. This takes at most
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
454 roughly lg(B) comparisons, and, unlike a straight binary search, favors
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
455 finding the right spot early in B (more on that later).
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
456
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
457 After finding such a k, the region of uncertainty is reduced to 2**(k-1) - 1
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
458 consecutive elements, and a straight binary search requires exactly k-1
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
459 additional comparisons to nail it. Then we copy all the B's up to that
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
460 point in one chunk, and then copy A[0]. Note that no matter where A[0]
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
461 belongs in B, the combination of galloping + binary search finds it in no
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
462 more than about 2*lg(B) comparisons.
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
463
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
464 If we did a straight binary search, we could find it in no more than
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
465 ceiling(lg(B+1)) comparisons -- but straight binary search takes that many
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
466 comparisons no matter where A[0] belongs. Straight binary search thus loses
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
467 to galloping unless the run is quite long, and we simply can't guess
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
468 whether it is in advance.
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
469
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
470 If data is random and runs have the same length, A[0] belongs at B[0] half
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
471 the time, at B[1] a quarter of the time, and so on: a consecutive winning
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
472 sub-run in B of length k occurs with probability 1/2**(k+1). So long
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
473 winning sub-runs are extremely unlikely in random data, and guessing that a
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
474 winning sub-run is going to be long is a dangerous game.
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
475
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
476 OTOH, if data is lopsided or lumpy or contains many duplicates, long
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
477 stretches of winning sub-runs are very likely, and cutting the number of
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
478 comparisons needed to find one from O(B) to O(log B) is a huge win.
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
479
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
480 Galloping compromises by getting out fast if there isn't a long winning
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
481 sub-run, yet finding such very efficiently when they exist.
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
482
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
483 I first learned about the galloping strategy in a related context; see:
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
484
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
485 "Adaptive Set Intersections, Unions, and Differences" (2000)
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
486 Erik D. Demaine, Alejandro López-Ortiz, J. Ian Munro
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
487
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
488 and its followup(s). An earlier paper called the same strategy
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
489 "exponential search":
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
490
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
491 "Optimistic Sorting and Information Theoretic Complexity"
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
492 Peter McIlroy
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
493 SODA (Fourth Annual ACM-SIAM Symposium on Discrete Algorithms), pp
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
494 467-474, Austin, Texas, 25-27 January 1993.
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
495
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
496 and it probably dates back to an earlier paper by Bentley and Yao. The
39338
82b6757ffff4 typo fix
Andrew M. Kuchling <amk@amk.ca>
parents: 35632
diff changeset
497 McIlroy paper in particular has good analysis of a mergesort that's
24455
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
498 probably strongly related to this one in its galloping strategy.
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
499
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
500
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
501 Galloping with a Broken Leg
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
502 ---------------------------
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
503 So why don't we always gallop? Because it can lose, on two counts:
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
504
24658
8bc265b084d9 Added info about highwater heap-memory use for the sortperf.py tests; + a
Tim Peters <tim.peters@gmail.com>
parents: 24455
diff changeset
505 1. While we're willing to endure small per-merge overheads, per-comparison
24455
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
506 overheads are a different story. Calling Yet Another Function per
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
507 comparison is expensive, and gallop_left() and gallop_right() are
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
508 too long-winded for sane inlining.
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
509
24658
8bc265b084d9 Added info about highwater heap-memory use for the sortperf.py tests; + a
Tim Peters <tim.peters@gmail.com>
parents: 24455
diff changeset
510 2. Galloping can-- alas --require more comparisons than linear one-at-time
8bc265b084d9 Added info about highwater heap-memory use for the sortperf.py tests; + a
Tim Peters <tim.peters@gmail.com>
parents: 24455
diff changeset
511 search, depending on the data.
24455
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
512
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
513 #2 requires details. If A[0] belongs before B[0], galloping requires 1
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
514 compare to determine that, same as linear search, except it costs more
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
515 to call the gallop function. If A[0] belongs right before B[1], galloping
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
516 requires 2 compares, again same as linear search. On the third compare,
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
517 galloping checks A[0] against B[3], and if it's <=, requires one more
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
518 compare to determine whether A[0] belongs at B[2] or B[3]. That's a total
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
519 of 4 compares, but if A[0] does belong at B[2], linear search would have
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
520 discovered that in only 3 compares, and that's a huge loss! Really. It's
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
521 an increase of 33% in the number of compares needed, and comparisons are
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
522 expensive in Python.
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
523
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
524 index in B where # compares linear # gallop # binary gallop
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
525 A[0] belongs search needs compares compares total
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
526 ---------------- ----------------- -------- -------- ------
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
527 0 1 1 0 1
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
528
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
529 1 2 2 0 2
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
530
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
531 2 3 3 1 4
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
532 3 4 3 1 4
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
533
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
534 4 5 4 2 6
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
535 5 6 4 2 6
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
536 6 7 4 2 6
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
537 7 8 4 2 6
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
538
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
539 8 9 5 3 8
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
540 9 10 5 3 8
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
541 10 11 5 3 8
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
542 11 12 5 3 8
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
543 ...
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
544
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
545 In general, if A[0] belongs at B[i], linear search requires i+1 comparisons
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
546 to determine that, and galloping a total of 2*floor(lg(i))+2 comparisons.
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
547 The advantage of galloping is unbounded as i grows, but it doesn't win at
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
548 all until i=6. Before then, it loses twice (at i=2 and i=4), and ties
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
549 at the other values. At and after i=6, galloping always wins.
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
550
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
551 We can't guess in advance when it's going to win, though, so we do one pair
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
552 at a time until the evidence seems strong that galloping may pay. MIN_GALLOP
24727
b5640e74aa5c 1. Combined the base and length arrays into a single array of structs.
Tim Peters <tim.peters@gmail.com>
parents: 24726
diff changeset
553 is 7, and that's pretty strong evidence. However, if the data is random, it
b5640e74aa5c 1. Combined the base and length arrays into a single array of structs.
Tim Peters <tim.peters@gmail.com>
parents: 24726
diff changeset
554 simply will trigger galloping mode purely by luck every now and again, and
b5640e74aa5c 1. Combined the base and length arrays into a single array of structs.
Tim Peters <tim.peters@gmail.com>
parents: 24726
diff changeset
555 it's quite likely to hit one of the losing cases next. On the other hand,
b5640e74aa5c 1. Combined the base and length arrays into a single array of structs.
Tim Peters <tim.peters@gmail.com>
parents: 24726
diff changeset
556 in cases like ~sort, galloping always pays, and MIN_GALLOP is larger than it
b5640e74aa5c 1. Combined the base and length arrays into a single array of structs.
Tim Peters <tim.peters@gmail.com>
parents: 24726
diff changeset
557 "should be" then. So the MergeState struct keeps a min_gallop variable
b5640e74aa5c 1. Combined the base and length arrays into a single array of structs.
Tim Peters <tim.peters@gmail.com>
parents: 24726
diff changeset
558 that merge_lo and merge_hi adjust: the longer we stay in galloping mode,
b5640e74aa5c 1. Combined the base and length arrays into a single array of structs.
Tim Peters <tim.peters@gmail.com>
parents: 24726
diff changeset
559 the smaller min_gallop gets, making it easier to transition back to
b5640e74aa5c 1. Combined the base and length arrays into a single array of structs.
Tim Peters <tim.peters@gmail.com>
parents: 24726
diff changeset
560 galloping mode (if we ever leave it in the current merge, and at the
b5640e74aa5c 1. Combined the base and length arrays into a single array of structs.
Tim Peters <tim.peters@gmail.com>
parents: 24726
diff changeset
561 start of the next merge). But whenever the gallop loop doesn't pay,
24730
8d850d58f109 Fixed new typos, added a little info about ~sort versus "hint"s.
Tim Peters <tim.peters@gmail.com>
parents: 24727
diff changeset
562 min_gallop is increased by one, making it harder to transition back
24727
b5640e74aa5c 1. Combined the base and length arrays into a single array of structs.
Tim Peters <tim.peters@gmail.com>
parents: 24726
diff changeset
563 to galloping mode (and again both within a merge and across merges). For
b5640e74aa5c 1. Combined the base and length arrays into a single array of structs.
Tim Peters <tim.peters@gmail.com>
parents: 24726
diff changeset
564 random data, this all but eliminates the gallop penalty: min_gallop grows
b5640e74aa5c 1. Combined the base and length arrays into a single array of structs.
Tim Peters <tim.peters@gmail.com>
parents: 24726
diff changeset
565 large enough that we almost never get into galloping mode. And for cases
b5640e74aa5c 1. Combined the base and length arrays into a single array of structs.
Tim Peters <tim.peters@gmail.com>
parents: 24726
diff changeset
566 like ~sort, min_gallop can fall to as low as 1. This seems to work well,
b5640e74aa5c 1. Combined the base and length arrays into a single array of structs.
Tim Peters <tim.peters@gmail.com>
parents: 24726
diff changeset
567 but in all it's a minor improvement over using a fixed MIN_GALLOP value.
24455
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
568
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
569
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
570 Galloping Complication
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
571 ----------------------
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
572 The description above was for merge_lo. merge_hi has to merge "from the
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
573 other end", and really needs to gallop starting at the last element in a run
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
574 instead of the first. Galloping from the first still works, but does more
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
575 comparisons than it should (this is significant -- I timed it both ways).
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
576 For this reason, the gallop_left() and gallop_right() functions have a
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
577 "hint" argument, which is the index at which galloping should begin. So
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
578 galloping can actually start at any index, and proceed at offsets of 1, 3,
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
579 7, 15, ... or -1, -3, -7, -15, ... from the starting index.
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
580
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
581 In the code as I type it's always called with either 0 or n-1 (where n is
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
582 the # of elements in a run). It's tempting to try to do something fancier,
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
583 melding galloping with some form of interpolation search; for example, if
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
584 we're merging a run of length 1 with a run of length 10000, index 5000 is
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
585 probably a better guess at the final result than either 0 or 9999. But
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
586 it's unclear how to generalize that intuition usefully, and merging of
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
587 wildly unbalanced runs already enjoys excellent performance.
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
588
24730
8d850d58f109 Fixed new typos, added a little info about ~sort versus "hint"s.
Tim Peters <tim.peters@gmail.com>
parents: 24727
diff changeset
589 ~sort is a good example of when balanced runs could benefit from a better
8d850d58f109 Fixed new typos, added a little info about ~sort versus "hint"s.
Tim Peters <tim.peters@gmail.com>
parents: 24727
diff changeset
590 hint value: to the extent possible, this would like to use a starting
8d850d58f109 Fixed new typos, added a little info about ~sort versus "hint"s.
Tim Peters <tim.peters@gmail.com>
parents: 24727
diff changeset
591 offset equal to the previous value of acount/bcount. Doing so saves about
8d850d58f109 Fixed new typos, added a little info about ~sort versus "hint"s.
Tim Peters <tim.peters@gmail.com>
parents: 24727
diff changeset
592 10% of the compares in ~sort. However, doing so is also a mixed bag,
8d850d58f109 Fixed new typos, added a little info about ~sort versus "hint"s.
Tim Peters <tim.peters@gmail.com>
parents: 24727
diff changeset
593 hurting other cases.
8d850d58f109 Fixed new typos, added a little info about ~sort versus "hint"s.
Tim Peters <tim.peters@gmail.com>
parents: 24727
diff changeset
594
24455
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
595
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
596 Comparing Average # of Compares on Random Arrays
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
597 ------------------------------------------------
24727
b5640e74aa5c 1. Combined the base and length arrays into a single array of structs.
Tim Peters <tim.peters@gmail.com>
parents: 24726
diff changeset
598 [NOTE: This was done when the new algorithm used about 0.1% more compares
b5640e74aa5c 1. Combined the base and length arrays into a single array of structs.
Tim Peters <tim.peters@gmail.com>
parents: 24726
diff changeset
599 on random data than does its current incarnation.]
b5640e74aa5c 1. Combined the base and length arrays into a single array of structs.
Tim Peters <tim.peters@gmail.com>
parents: 24726
diff changeset
600
24455
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
601 Here list.sort() is samplesort, and list.msort() this sort:
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
602
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
603 """
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
604 import random
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
605 from time import clock as now
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
606
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
607 def fill(n):
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
608 from random import random
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
609 return [random() for i in xrange(n)]
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
610
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
611 def mycmp(x, y):
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
612 global ncmp
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
613 ncmp += 1
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
614 return cmp(x, y)
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
615
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
616 def timeit(values, method):
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
617 global ncmp
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
618 X = values[:]
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
619 bound = getattr(X, method)
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
620 ncmp = 0
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
621 t1 = now()
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
622 bound(mycmp)
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
623 t2 = now()
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
624 return t2-t1, ncmp
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
625
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
626 format = "%5s %9.2f %11d"
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
627 f2 = "%5s %9.2f %11.2f"
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
628
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
629 def drive():
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
630 count = sst = sscmp = mst = mscmp = nelts = 0
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
631 while True:
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
632 n = random.randrange(100000)
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
633 nelts += n
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
634 x = fill(n)
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
635
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
636 t, c = timeit(x, 'sort')
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
637 sst += t
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
638 sscmp += c
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
639
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
640 t, c = timeit(x, 'msort')
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
641 mst += t
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
642 mscmp += c
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
643
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
644 count += 1
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
645 if count % 10:
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
646 continue
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
647
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
648 print "count", count, "nelts", nelts
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
649 print format % ("sort", sst, sscmp)
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
650 print format % ("msort", mst, mscmp)
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
651 print f2 % ("", (sst-mst)*1e2/mst, (sscmp-mscmp)*1e2/mscmp)
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
652
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
653 drive()
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
654 """
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
655
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
656 I ran this on Windows and kept using the computer lightly while it was
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
657 running. time.clock() is wall-clock time on Windows, with better than
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
658 microsecond resolution. samplesort started with a 1.52% #-of-comparisons
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
659 disadvantage, fell quickly to 1.48%, and then fluctuated within that small
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
660 range. Here's the last chunk of output before I killed the job:
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
661
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
662 count 2630 nelts 130906543
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
663 sort 6110.80 1937887573
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
664 msort 6002.78 1909389381
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
665 1.80 1.49
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
666
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
667 We've done nearly 2 billion comparisons apiece at Python speed there, and
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
668 that's enough <wink>.
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
669
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
670 For random arrays of size 2 (yes, there are only 2 interesting ones),
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
671 samplesort has a 50%(!) comparison disadvantage. This is a consequence of
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
672 samplesort special-casing at most one ascending run at the start, then
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
673 falling back to the general case if it doesn't find an ascending run
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
674 immediately. The consequence is that it ends up using two compares to sort
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
675 [2, 1]. Gratifyingly, timsort doesn't do any special-casing, so had to be
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
676 taught how to deal with mixtures of ascending and descending runs
d971b8703508 Checking in the doc file for "timsort". There's way too much here to
Tim Peters <tim.peters@gmail.com>
parents:
diff changeset
677 efficiently in all cases.