1 // Copyright 2009 The Go Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file.
5 //go:generate go run genzfunc.go
7 // Package sort provides primitives for sorting slices and user-defined
11 // A type, typically a collection, that satisfies sort.Interface can be
12 // sorted by the routines in this package. The methods require that the
13 // elements of the collection be enumerated by an integer index.
14 type Interface
interface {
15 // Len is the number of elements in the collection.
17 // Less reports whether the element with
18 // index i should sort before the element with index j.
20 // Swap swaps the elements with indexes i and j.
25 func insertionSort(data Interface
, a
, b
int) {
26 for i
:= a
+ 1; i
< b
; i
++ {
27 for j
:= i
; j
> a
&& data
.Less(j
, j
-1); j
-- {
33 // siftDown implements the heap property on data[lo, hi).
34 // first is an offset into the array where the root of the heap lies.
35 func siftDown(data Interface
, lo
, hi
, first
int) {
42 if child
+1 < hi
&& data
.Less(first
+child
, first
+child
+1) {
45 if !data
.Less(first
+root
, first
+child
) {
48 data
.Swap(first
+root
, first
+child
)
53 func heapSort(data Interface
, a
, b
int) {
58 // Build heap with greatest element at top.
59 for i
:= (hi
- 1) / 2; i
>= 0; i
-- {
60 siftDown(data
, i
, hi
, first
)
63 // Pop elements, largest first, into end of data.
64 for i
:= hi
- 1; i
>= 0; i
-- {
65 data
.Swap(first
, first
+i
)
66 siftDown(data
, lo
, i
, first
)
70 // Quicksort, loosely following Bentley and McIlroy,
71 // ``Engineering a Sort Function,'' SP&E November 1993.
73 // medianOfThree moves the median of the three values data[m0], data[m1], data[m2] into data[m1].
74 func medianOfThree(data Interface
, m1
, m0
, m2
int) {
76 if data
.Less(m1
, m0
) {
79 // data[m0] <= data[m1]
80 if data
.Less(m2
, m1
) {
82 // data[m0] <= data[m2] && data[m1] < data[m2]
83 if data
.Less(m1
, m0
) {
87 // now data[m0] <= data[m1] <= data[m2]
90 func swapRange(data Interface
, a
, b
, n
int) {
91 for i
:= 0; i
< n
; i
++ {
96 func doPivot(data Interface
, lo
, hi
int) (midlo
, midhi
int) {
97 m
:= int(uint(lo
+hi
) >> 1) // Written like this to avoid integer overflow.
99 // Tukey's ``Ninther,'' median of three medians of three.
101 medianOfThree(data
, lo
, lo
+s
, lo
+2*s
)
102 medianOfThree(data
, m
, m
-s
, m
+s
)
103 medianOfThree(data
, hi
-1, hi
-1-s
, hi
-1-2*s
)
105 medianOfThree(data
, lo
, m
, hi
-1)
108 // data[lo] = pivot (set up by ChoosePivot)
109 // data[lo < i < a] < pivot
110 // data[a <= i < b] <= pivot
111 // data[b <= i < c] unexamined
112 // data[c <= i < hi-1] > pivot
113 // data[hi-1] >= pivot
117 for ; a
< c
&& data
.Less(a
, pivot
); a
++ {
121 for ; b
< c
&& !data
.Less(pivot
, b
); b
++ { // data[b] <= pivot
123 for ; b
< c
&& data
.Less(pivot
, c
-1); c
-- { // data[c-1] > pivot
128 // data[b] > pivot; data[c-1] <= pivot
133 // If hi-c<3 then there are duplicates (by property of median of nine).
134 // Let be a bit more conservative, and set border to 5.
136 if !protect
&& hi
-c
< (hi
-lo
)/4 {
137 // Lets test some points for equality to pivot
139 if !data
.Less(pivot
, hi
-1) { // data[hi-1] = pivot
144 if !data
.Less(b
-1, pivot
) { // data[b-1] = pivot
148 // m-lo = (hi-lo)/2 > 6
149 // b-lo > (hi-lo)*3/4-1 > 8
150 // ==> m < b ==> data[m] <= pivot
151 if !data
.Less(m
, pivot
) { // data[m] = pivot
156 // if at least 2 points are equal to pivot, assume skewed distribution
160 // Protect against a lot of duplicates
162 // data[a <= i < b] unexamined
163 // data[b <= i < c] = pivot
165 for ; a
< b
&& !data
.Less(b
-1, pivot
); b
-- { // data[b] == pivot
167 for ; a
< b
&& data
.Less(a
, pivot
); a
++ { // data[a] < pivot
172 // data[a] == pivot; data[b-1] < pivot
178 // Swap pivot into middle
179 data
.Swap(pivot
, b
-1)
183 func quickSort(data Interface
, a
, b
, maxDepth
int) {
184 for b
-a
> 12 { // Use ShellSort for slices <= 12 elements
190 mlo
, mhi
:= doPivot(data
, a
, b
)
191 // Avoiding recursion on the larger subproblem guarantees
192 // a stack depth of at most lg(b-a).
194 quickSort(data
, a
, mlo
, maxDepth
)
195 a
= mhi
// i.e., quickSort(data, mhi, b)
197 quickSort(data
, mhi
, b
, maxDepth
)
198 b
= mlo
// i.e., quickSort(data, a, mlo)
202 // Do ShellSort pass with gap 6
203 // It could be written in this simplified form cause b-a <= 12
204 for i
:= a
+ 6; i
< b
; i
++ {
205 if data
.Less(i
, i
-6) {
209 insertionSort(data
, a
, b
)
214 // It makes one call to data.Len to determine n, and O(n*log(n)) calls to
215 // data.Less and data.Swap. The sort is not guaranteed to be stable.
216 func Sort(data Interface
) {
218 quickSort(data
, 0, n
, maxDepth(n
))
221 // maxDepth returns a threshold at which quicksort should switch
222 // to heapsort. It returns 2*ceil(lg(n+1)).
223 func maxDepth(n
int) int {
225 for i
:= n
; i
> 0; i
>>= 1 {
231 // lessSwap is a pair of Less and Swap function for use with the
232 // auto-generated func-optimized variant of sort.go in
234 type lessSwap
struct {
235 Less
func(i
, j
int) bool
239 type reverse
struct {
240 // This embedded Interface permits Reverse to use the methods of
241 // another Interface implementation.
245 // Less returns the opposite of the embedded implementation's Less method.
246 func (r reverse
) Less(i
, j
int) bool {
247 return r
.Interface
.Less(j
, i
)
250 // Reverse returns the reverse order for data.
251 func Reverse(data Interface
) Interface
{
252 return &reverse
{data
}
255 // IsSorted reports whether data is sorted.
256 func IsSorted(data Interface
) bool {
258 for i
:= n
- 1; i
> 0; i
-- {
259 if data
.Less(i
, i
-1) {
266 // Convenience types for common cases
268 // IntSlice attaches the methods of Interface to []int, sorting in increasing order.
271 func (p IntSlice
) Len() int { return len(p
) }
272 func (p IntSlice
) Less(i
, j
int) bool { return p
[i
] < p
[j
] }
273 func (p IntSlice
) Swap(i
, j
int) { p
[i
], p
[j
] = p
[j
], p
[i
] }
275 // Sort is a convenience method.
276 func (p IntSlice
) Sort() { Sort(p
) }
278 // Float64Slice attaches the methods of Interface to []float64, sorting in increasing order
279 // (not-a-number values are treated as less than other values).
280 type Float64Slice
[]float64
282 func (p Float64Slice
) Len() int { return len(p
) }
283 func (p Float64Slice
) Less(i
, j
int) bool { return p
[i
] < p
[j
] ||
isNaN(p
[i
]) && !isNaN(p
[j
]) }
284 func (p Float64Slice
) Swap(i
, j
int) { p
[i
], p
[j
] = p
[j
], p
[i
] }
286 // isNaN is a copy of math.IsNaN to avoid a dependency on the math package.
287 func isNaN(f
float64) bool {
291 // Sort is a convenience method.
292 func (p Float64Slice
) Sort() { Sort(p
) }
294 // StringSlice attaches the methods of Interface to []string, sorting in increasing order.
295 type StringSlice
[]string
297 func (p StringSlice
) Len() int { return len(p
) }
298 func (p StringSlice
) Less(i
, j
int) bool { return p
[i
] < p
[j
] }
299 func (p StringSlice
) Swap(i
, j
int) { p
[i
], p
[j
] = p
[j
], p
[i
] }
301 // Sort is a convenience method.
302 func (p StringSlice
) Sort() { Sort(p
) }
304 // Convenience wrappers for common cases
306 // Ints sorts a slice of ints in increasing order.
307 func Ints(a
[]int) { Sort(IntSlice(a
)) }
309 // Float64s sorts a slice of float64s in increasing order
310 // (not-a-number values are treated as less than other values).
311 func Float64s(a
[]float64) { Sort(Float64Slice(a
)) }
313 // Strings sorts a slice of strings in increasing order.
314 func Strings(a
[]string) { Sort(StringSlice(a
)) }
316 // IntsAreSorted tests whether a slice of ints is sorted in increasing order.
317 func IntsAreSorted(a
[]int) bool { return IsSorted(IntSlice(a
)) }
319 // Float64sAreSorted tests whether a slice of float64s is sorted in increasing order
320 // (not-a-number values are treated as less than other values).
321 func Float64sAreSorted(a
[]float64) bool { return IsSorted(Float64Slice(a
)) }
323 // StringsAreSorted tests whether a slice of strings is sorted in increasing order.
324 func StringsAreSorted(a
[]string) bool { return IsSorted(StringSlice(a
)) }
326 // Notes on stable sorting:
327 // The used algorithms are simple and provable correct on all input and use
328 // only logarithmic additional stack space. They perform well if compared
329 // experimentally to other stable in-place sorting algorithms.
331 // Remarks on other algorithms evaluated:
332 // - GCC's 4.6.3 stable_sort with merge_without_buffer from libstdc++:
334 // - GCC's __rotate for block rotations: Not faster.
335 // - "Practical in-place mergesort" from Jyrki Katajainen, Tomi A. Pasanen
336 // and Jukka Teuhola; Nordic Journal of Computing 3,1 (1996), 27-40:
337 // The given algorithms are in-place, number of Swap and Assignments
338 // grow as n log n but the algorithm is not stable.
339 // - "Fast Stable In-Place Sorting with O(n) Data Moves" J.I. Munro and
340 // V. Raman in Algorithmica (1996) 16, 115-160:
341 // This algorithm either needs additional 2n bits or works only if there
342 // are enough different elements available to encode some permutations
343 // which have to be undone later (so not stable on any input).
344 // - All the optimal in-place sorting/merging algorithms I found are either
345 // unstable or rely on enough different elements in each step to encode the
346 // performed block rearrangements. See also "In-Place Merging Algorithms",
347 // Denham Coates-Evely, Department of Computer Science, Kings College,
348 // January 2004 and the references in there.
349 // - Often "optimal" algorithms are optimal in the number of assignments
350 // but Interface has only Swap as operation.
352 // Stable sorts data while keeping the original order of equal elements.
354 // It makes one call to data.Len to determine n, O(n*log(n)) calls to
355 // data.Less and O(n*log(n)*log(n)) calls to data.Swap.
356 func Stable(data Interface
) {
357 stable(data
, data
.Len())
360 func stable(data Interface
, n
int) {
361 blockSize
:= 20 // must be > 0
364 insertionSort(data
, a
, b
)
368 insertionSort(data
, a
, n
)
371 a
, b
= 0, 2*blockSize
373 symMerge(data
, a
, a
+blockSize
, b
)
377 if m
:= a
+ blockSize
; m
< n
{
378 symMerge(data
, a
, m
, n
)
384 // SymMerge merges the two sorted subsequences data[a:m] and data[m:b] using
385 // the SymMerge algorithm from Pok-Son Kim and Arne Kutzner, "Stable Minimum
386 // Storage Merging by Symmetric Comparisons", in Susanne Albers and Tomasz
387 // Radzik, editors, Algorithms - ESA 2004, volume 3221 of Lecture Notes in
388 // Computer Science, pages 714-723. Springer, 2004.
390 // Let M = m-a and N = b-n. Wolog M < N.
391 // The recursion depth is bound by ceil(log(N+M)).
392 // The algorithm needs O(M*log(N/M + 1)) calls to data.Less.
393 // The algorithm needs O((M+N)*log(M)) calls to data.Swap.
395 // The paper gives O((M+N)*log(M)) as the number of assignments assuming a
396 // rotation algorithm which uses O(M+N+gcd(M+N)) assignments. The argumentation
397 // in the paper carries through for Swap operations, especially as the block
398 // swapping rotate uses only O(M+N) Swaps.
400 // symMerge assumes non-degenerate arguments: a < m && m < b.
401 // Having the caller check this condition eliminates many leaf recursion calls,
402 // which improves performance.
403 func symMerge(data Interface
, a
, m
, b
int) {
404 // Avoid unnecessary recursions of symMerge
405 // by direct insertion of data[a] into data[m:b]
406 // if data[a:m] only contains one element.
408 // Use binary search to find the lowest index i
409 // such that data[i] >= data[a] for m <= i < b.
410 // Exit the search loop with i == b in case no such index exists.
414 h
:= int(uint(i
+j
) >> 1)
421 // Swap values until data[a] reaches the position before i.
422 for k
:= a
; k
< i
-1; k
++ {
428 // Avoid unnecessary recursions of symMerge
429 // by direct insertion of data[m] into data[a:m]
430 // if data[m:b] only contains one element.
432 // Use binary search to find the lowest index i
433 // such that data[i] > data[m] for a <= i < m.
434 // Exit the search loop with i == m in case no such index exists.
438 h
:= int(uint(i
+j
) >> 1)
439 if !data
.Less(m
, h
) {
445 // Swap values until data[m] reaches the position i.
446 for k
:= m
; k
> i
; k
-- {
452 mid
:= int(uint(a
+b
) >> 1)
465 c
:= int(uint(start
+r
) >> 1)
466 if !data
.Less(p
-c
, c
) {
474 if start
< m
&& m
< end
{
475 rotate(data
, start
, m
, end
)
477 if a
< start
&& start
< mid
{
478 symMerge(data
, a
, start
, mid
)
480 if mid
< end
&& end
< b
{
481 symMerge(data
, mid
, end
, b
)
485 // Rotate two consecutive blocks u = data[a:m] and v = data[m:b] in data:
486 // Data of the form 'x u v y' is changed to 'x v u y'.
487 // Rotate performs at most b-a many calls to data.Swap.
488 // Rotate assumes non-degenerate arguments: a < m && m < b.
489 func rotate(data Interface
, a
, m
, b
int) {
495 swapRange(data
, m
-i
, m
, j
)
498 swapRange(data
, m
-i
, m
+j
-i
, i
)
503 swapRange(data
, m
-i
, m
, i
)
507 Complexity of Stable Sorting
510 Complexity of block swapping rotation
512 Each Swap puts one new element into its correct, final position.
513 Elements which reach their final position are no longer moved.
514 Thus block swapping rotation needs |u|+|v| calls to Swaps.
515 This is best possible as each element might need a move.
517 Pay attention when comparing to other optimal algorithms which
518 typically count the number of assignments instead of swaps:
519 E.g. the optimal algorithm of Dudzinski and Dydek for in-place
520 rotations uses O(u + v + gcd(u,v)) assignments which is
521 better than our O(3 * (u+v)) as gcd(u,v) <= u.
524 Stable sorting by SymMerge and BlockSwap rotations
526 SymMerg complexity for same size input M = N:
527 Calls to Less: O(M*log(N/M+1)) = O(N*log(2)) = O(N)
528 Calls to Swap: O((M+N)*log(M)) = O(2*N*log(N)) = O(N*log(N))
530 (The following argument does not fuzz over a missing -1 or
531 other stuff which does not impact the final result).
533 Let n = data.Len(). Assume n = 2^k.
535 Plain merge sort performs log(n) = k iterations.
536 On iteration i the algorithm merges 2^(k-i) blocks, each of size 2^i.
538 Thus iteration i of merge sort performs:
539 Calls to Less O(2^(k-i) * 2^i) = O(2^k) = O(2^log(n)) = O(n)
540 Calls to Swap O(2^(k-i) * 2^i * log(2^i)) = O(2^k * i) = O(n*i)
542 In total k = log(n) iterations are performed; so in total:
543 Calls to Less O(log(n) * n)
544 Calls to Swap O(n + 2*n + 3*n + ... + (k-1)*n + k*n)
545 = O((k/2) * k * n) = O(n * k^2) = O(n * log^2(n))
548 Above results should generalize to arbitrary n = 2^k + p
549 and should not be influenced by the initial insertion sort phase:
550 Insertion sort is O(n^2) on Swap and Less, thus O(bs^2) per block of
551 size bs at n/bs blocks: O(bs*n) Swaps and Less during insertion sort.
552 Merge sort iterations start at i = log(bs). With t = log(bs) constant:
553 Calls to Less O((log(n)-t) * n + bs*n) = O(log(n)*n + (bs-t)*n)
555 Calls to Swap O(n * log^2(n) - (t^2+t)/2*n) = O(n * log^2(n))