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
13 // A type, typically a collection, that satisfies sort.Interface can be
14 // sorted by the routines in this package. The methods require that the
15 // elements of the collection be enumerated by an integer index.
16 type Interface
interface {
17 // Len is the number of elements in the collection.
19 // Less reports whether the element with
20 // index i should sort before the element with index j.
22 // Swap swaps the elements with indexes i and j.
27 func insertionSort(data Interface
, a
, b
int) {
28 for i
:= a
+ 1; i
< b
; i
++ {
29 for j
:= i
; j
> a
&& data
.Less(j
, j
-1); j
-- {
35 // siftDown implements the heap property on data[lo, hi).
36 // first is an offset into the array where the root of the heap lies.
37 func siftDown(data Interface
, lo
, hi
, first
int) {
44 if child
+1 < hi
&& data
.Less(first
+child
, first
+child
+1) {
47 if !data
.Less(first
+root
, first
+child
) {
50 data
.Swap(first
+root
, first
+child
)
55 func heapSort(data Interface
, a
, b
int) {
60 // Build heap with greatest element at top.
61 for i
:= (hi
- 1) / 2; i
>= 0; i
-- {
62 siftDown(data
, i
, hi
, first
)
65 // Pop elements, largest first, into end of data.
66 for i
:= hi
- 1; i
>= 0; i
-- {
67 data
.Swap(first
, first
+i
)
68 siftDown(data
, lo
, i
, first
)
72 // Quicksort, loosely following Bentley and McIlroy,
73 // ``Engineering a Sort Function,'' SP&E November 1993.
75 // medianOfThree moves the median of the three values data[m0], data[m1], data[m2] into data[m1].
76 func medianOfThree(data Interface
, m1
, m0
, m2
int) {
78 if data
.Less(m1
, m0
) {
81 // data[m0] <= data[m1]
82 if data
.Less(m2
, m1
) {
84 // data[m0] <= data[m2] && data[m1] < data[m2]
85 if data
.Less(m1
, m0
) {
89 // now data[m0] <= data[m1] <= data[m2]
92 func swapRange(data Interface
, a
, b
, n
int) {
93 for i
:= 0; i
< n
; i
++ {
98 func doPivot(data Interface
, lo
, hi
int) (midlo
, midhi
int) {
99 m
:= lo
+ (hi
-lo
)/2 // Written like this to avoid integer overflow.
101 // Tukey's ``Ninther,'' median of three medians of three.
103 medianOfThree(data
, lo
, lo
+s
, lo
+2*s
)
104 medianOfThree(data
, m
, m
-s
, m
+s
)
105 medianOfThree(data
, hi
-1, hi
-1-s
, hi
-1-2*s
)
107 medianOfThree(data
, lo
, m
, hi
-1)
110 // data[lo] = pivot (set up by ChoosePivot)
111 // data[lo < i < a] < pivot
112 // data[a <= i < b] <= pivot
113 // data[b <= i < c] unexamined
114 // data[c <= i < hi-1] > pivot
115 // data[hi-1] >= pivot
119 for ; a
< c
&& data
.Less(a
, pivot
); a
++ {
123 for ; b
< c
&& !data
.Less(pivot
, b
); b
++ { // data[b] <= pivot
125 for ; b
< c
&& data
.Less(pivot
, c
-1); c
-- { // data[c-1] > pivot
130 // data[b] > pivot; data[c-1] <= pivot
135 // If hi-c<3 then there are duplicates (by property of median of nine).
136 // Let be a bit more conservative, and set border to 5.
138 if !protect
&& hi
-c
< (hi
-lo
)/4 {
139 // Lets test some points for equality to pivot
141 if !data
.Less(pivot
, hi
-1) { // data[hi-1] = pivot
146 if !data
.Less(b
-1, pivot
) { // data[b-1] = pivot
150 // m-lo = (hi-lo)/2 > 6
151 // b-lo > (hi-lo)*3/4-1 > 8
152 // ==> m < b ==> data[m] <= pivot
153 if !data
.Less(m
, pivot
) { // data[m] = pivot
158 // if at least 2 points are equal to pivot, assume skewed distribution
162 // Protect against a lot of duplicates
164 // data[a <= i < b] unexamined
165 // data[b <= i < c] = pivot
167 for ; a
< b
&& !data
.Less(b
-1, pivot
); b
-- { // data[b] == pivot
169 for ; a
< b
&& data
.Less(a
, pivot
); a
++ { // data[a] < pivot
174 // data[a] == pivot; data[b-1] < pivot
180 // Swap pivot into middle
181 data
.Swap(pivot
, b
-1)
185 func quickSort(data Interface
, a
, b
, maxDepth
int) {
186 for b
-a
> 12 { // Use ShellSort for slices <= 12 elements
192 mlo
, mhi
:= doPivot(data
, a
, b
)
193 // Avoiding recursion on the larger subproblem guarantees
194 // a stack depth of at most lg(b-a).
196 quickSort(data
, a
, mlo
, maxDepth
)
197 a
= mhi
// i.e., quickSort(data, mhi, b)
199 quickSort(data
, mhi
, b
, maxDepth
)
200 b
= mlo
// i.e., quickSort(data, a, mlo)
204 // Do ShellSort pass with gap 6
205 // It could be written in this simplified form cause b-a <= 12
206 for i
:= a
+ 6; i
< b
; i
++ {
207 if data
.Less(i
, i
-6) {
211 insertionSort(data
, a
, b
)
216 // It makes one call to data.Len to determine n, and O(n*log(n)) calls to
217 // data.Less and data.Swap. The sort is not guaranteed to be stable.
218 func Sort(data Interface
) {
220 quickSort(data
, 0, n
, maxDepth(n
))
223 // maxDepth returns a threshold at which quicksort should switch
224 // to heapsort. It returns 2*ceil(lg(n+1)).
225 func maxDepth(n
int) int {
227 for i
:= n
; i
> 0; i
>>= 1 {
233 // lessSwap is a pair of Less and Swap function for use with the
234 // auto-generated func-optimized variant of sort.go in
236 type lessSwap
struct {
237 Less
func(i
, j
int) bool
241 // Slice sorts the provided slice given the provided less function.
243 // The sort is not guaranteed to be stable. For a stable sort, use
246 // The function panics if the provided interface is not a slice.
247 func Slice(slice
interface{}, less
func(i
, j
int) bool) {
248 rv
:= reflect
.ValueOf(slice
)
249 swap
:= reflect
.Swapper(slice
)
251 quickSort_func(lessSwap
{less
, swap
}, 0, length
, maxDepth(length
))
254 // SliceStable sorts the provided slice given the provided less
255 // function while keeping the original order of equal elements.
257 // The function panics if the provided interface is not a slice.
258 func SliceStable(slice
interface{}, less
func(i
, j
int) bool) {
259 rv
:= reflect
.ValueOf(slice
)
260 swap
:= reflect
.Swapper(slice
)
261 stable_func(lessSwap
{less
, swap
}, rv
.Len())
264 // SliceIsSorted tests whether a slice is sorted.
266 // The function panics if the provided interface is not a slice.
267 func SliceIsSorted(slice
interface{}, less
func(i
, j
int) bool) bool {
268 rv
:= reflect
.ValueOf(slice
)
270 for i
:= n
- 1; i
> 0; i
-- {
278 type reverse
struct {
279 // This embedded Interface permits Reverse to use the methods of
280 // another Interface implementation.
284 // Less returns the opposite of the embedded implementation's Less method.
285 func (r reverse
) Less(i
, j
int) bool {
286 return r
.Interface
.Less(j
, i
)
289 // Reverse returns the reverse order for data.
290 func Reverse(data Interface
) Interface
{
291 return &reverse
{data
}
294 // IsSorted reports whether data is sorted.
295 func IsSorted(data Interface
) bool {
297 for i
:= n
- 1; i
> 0; i
-- {
298 if data
.Less(i
, i
-1) {
305 // Convenience types for common cases
307 // IntSlice attaches the methods of Interface to []int, sorting in increasing order.
310 func (p IntSlice
) Len() int { return len(p
) }
311 func (p IntSlice
) Less(i
, j
int) bool { return p
[i
] < p
[j
] }
312 func (p IntSlice
) Swap(i
, j
int) { p
[i
], p
[j
] = p
[j
], p
[i
] }
314 // Sort is a convenience method.
315 func (p IntSlice
) Sort() { Sort(p
) }
317 // Float64Slice attaches the methods of Interface to []float64, sorting in increasing order.
318 type Float64Slice
[]float64
320 func (p Float64Slice
) Len() int { return len(p
) }
321 func (p Float64Slice
) Less(i
, j
int) bool { return p
[i
] < p
[j
] ||
isNaN(p
[i
]) && !isNaN(p
[j
]) }
322 func (p Float64Slice
) Swap(i
, j
int) { p
[i
], p
[j
] = p
[j
], p
[i
] }
324 // isNaN is a copy of math.IsNaN to avoid a dependency on the math package.
325 func isNaN(f
float64) bool {
329 // Sort is a convenience method.
330 func (p Float64Slice
) Sort() { Sort(p
) }
332 // StringSlice attaches the methods of Interface to []string, sorting in increasing order.
333 type StringSlice
[]string
335 func (p StringSlice
) Len() int { return len(p
) }
336 func (p StringSlice
) Less(i
, j
int) bool { return p
[i
] < p
[j
] }
337 func (p StringSlice
) Swap(i
, j
int) { p
[i
], p
[j
] = p
[j
], p
[i
] }
339 // Sort is a convenience method.
340 func (p StringSlice
) Sort() { Sort(p
) }
342 // Convenience wrappers for common cases
344 // Ints sorts a slice of ints in increasing order.
345 func Ints(a
[]int) { Sort(IntSlice(a
)) }
347 // Float64s sorts a slice of float64s in increasing order.
348 func Float64s(a
[]float64) { Sort(Float64Slice(a
)) }
350 // Strings sorts a slice of strings in increasing order.
351 func Strings(a
[]string) { Sort(StringSlice(a
)) }
353 // IntsAreSorted tests whether a slice of ints is sorted in increasing order.
354 func IntsAreSorted(a
[]int) bool { return IsSorted(IntSlice(a
)) }
356 // Float64sAreSorted tests whether a slice of float64s is sorted in increasing order.
357 func Float64sAreSorted(a
[]float64) bool { return IsSorted(Float64Slice(a
)) }
359 // StringsAreSorted tests whether a slice of strings is sorted in increasing order.
360 func StringsAreSorted(a
[]string) bool { return IsSorted(StringSlice(a
)) }
362 // Notes on stable sorting:
363 // The used algorithms are simple and provable correct on all input and use
364 // only logarithmic additional stack space. They perform well if compared
365 // experimentally to other stable in-place sorting algorithms.
367 // Remarks on other algorithms evaluated:
368 // - GCC's 4.6.3 stable_sort with merge_without_buffer from libstdc++:
370 // - GCC's __rotate for block rotations: Not faster.
371 // - "Practical in-place mergesort" from Jyrki Katajainen, Tomi A. Pasanen
372 // and Jukka Teuhola; Nordic Journal of Computing 3,1 (1996), 27-40:
373 // The given algorithms are in-place, number of Swap and Assignments
374 // grow as n log n but the algorithm is not stable.
375 // - "Fast Stable In-Place Sorting with O(n) Data Moves" J.I. Munro and
376 // V. Raman in Algorithmica (1996) 16, 115-160:
377 // This algorithm either needs additional 2n bits or works only if there
378 // are enough different elements available to encode some permutations
379 // which have to be undone later (so not stable on any input).
380 // - All the optimal in-place sorting/merging algorithms I found are either
381 // unstable or rely on enough different elements in each step to encode the
382 // performed block rearrangements. See also "In-Place Merging Algorithms",
383 // Denham Coates-Evely, Department of Computer Science, Kings College,
384 // January 2004 and the references in there.
385 // - Often "optimal" algorithms are optimal in the number of assignments
386 // but Interface has only Swap as operation.
388 // Stable sorts data while keeping the original order of equal elements.
390 // It makes one call to data.Len to determine n, O(n*log(n)) calls to
391 // data.Less and O(n*log(n)*log(n)) calls to data.Swap.
392 func Stable(data Interface
) {
393 stable(data
, data
.Len())
396 func stable(data Interface
, n
int) {
397 blockSize
:= 20 // must be > 0
400 insertionSort(data
, a
, b
)
404 insertionSort(data
, a
, n
)
407 a
, b
= 0, 2*blockSize
409 symMerge(data
, a
, a
+blockSize
, b
)
413 if m
:= a
+ blockSize
; m
< n
{
414 symMerge(data
, a
, m
, n
)
420 // SymMerge merges the two sorted subsequences data[a:m] and data[m:b] using
421 // the SymMerge algorithm from Pok-Son Kim and Arne Kutzner, "Stable Minimum
422 // Storage Merging by Symmetric Comparisons", in Susanne Albers and Tomasz
423 // Radzik, editors, Algorithms - ESA 2004, volume 3221 of Lecture Notes in
424 // Computer Science, pages 714-723. Springer, 2004.
426 // Let M = m-a and N = b-n. Wolog M < N.
427 // The recursion depth is bound by ceil(log(N+M)).
428 // The algorithm needs O(M*log(N/M + 1)) calls to data.Less.
429 // The algorithm needs O((M+N)*log(M)) calls to data.Swap.
431 // The paper gives O((M+N)*log(M)) as the number of assignments assuming a
432 // rotation algorithm which uses O(M+N+gcd(M+N)) assignments. The argumentation
433 // in the paper carries through for Swap operations, especially as the block
434 // swapping rotate uses only O(M+N) Swaps.
436 // symMerge assumes non-degenerate arguments: a < m && m < b.
437 // Having the caller check this condition eliminates many leaf recursion calls,
438 // which improves performance.
439 func symMerge(data Interface
, a
, m
, b
int) {
440 // Avoid unnecessary recursions of symMerge
441 // by direct insertion of data[a] into data[m:b]
442 // if data[a:m] only contains one element.
444 // Use binary search to find the lowest index i
445 // such that data[i] >= data[a] for m <= i < b.
446 // Exit the search loop with i == b in case no such index exists.
457 // Swap values until data[a] reaches the position before i.
458 for k
:= a
; k
< i
-1; k
++ {
464 // Avoid unnecessary recursions of symMerge
465 // by direct insertion of data[m] into data[a:m]
466 // if data[m:b] only contains one element.
468 // Use binary search to find the lowest index i
469 // such that data[i] > data[m] for a <= i < m.
470 // Exit the search loop with i == m in case no such index exists.
475 if !data
.Less(m
, h
) {
481 // Swap values until data[m] reaches the position i.
482 for k
:= m
; k
> i
; k
-- {
501 c
:= start
+ (r
-start
)/2
502 if !data
.Less(p
-c
, c
) {
510 if start
< m
&& m
< end
{
511 rotate(data
, start
, m
, end
)
513 if a
< start
&& start
< mid
{
514 symMerge(data
, a
, start
, mid
)
516 if mid
< end
&& end
< b
{
517 symMerge(data
, mid
, end
, b
)
521 // Rotate two consecutives blocks u = data[a:m] and v = data[m:b] in data:
522 // Data of the form 'x u v y' is changed to 'x v u y'.
523 // Rotate performs at most b-a many calls to data.Swap.
524 // Rotate assumes non-degenerate arguments: a < m && m < b.
525 func rotate(data Interface
, a
, m
, b
int) {
531 swapRange(data
, m
-i
, m
, j
)
534 swapRange(data
, m
-i
, m
+j
-i
, i
)
539 swapRange(data
, m
-i
, m
, i
)
543 Complexity of Stable Sorting
546 Complexity of block swapping rotation
548 Each Swap puts one new element into its correct, final position.
549 Elements which reach their final position are no longer moved.
550 Thus block swapping rotation needs |u|+|v| calls to Swaps.
551 This is best possible as each element might need a move.
553 Pay attention when comparing to other optimal algorithms which
554 typically count the number of assignments instead of swaps:
555 E.g. the optimal algorithm of Dudzinski and Dydek for in-place
556 rotations uses O(u + v + gcd(u,v)) assignments which is
557 better than our O(3 * (u+v)) as gcd(u,v) <= u.
560 Stable sorting by SymMerge and BlockSwap rotations
562 SymMerg complexity for same size input M = N:
563 Calls to Less: O(M*log(N/M+1)) = O(N*log(2)) = O(N)
564 Calls to Swap: O((M+N)*log(M)) = O(2*N*log(N)) = O(N*log(N))
566 (The following argument does not fuzz over a missing -1 or
567 other stuff which does not impact the final result).
569 Let n = data.Len(). Assume n = 2^k.
571 Plain merge sort performs log(n) = k iterations.
572 On iteration i the algorithm merges 2^(k-i) blocks, each of size 2^i.
574 Thus iteration i of merge sort performs:
575 Calls to Less O(2^(k-i) * 2^i) = O(2^k) = O(2^log(n)) = O(n)
576 Calls to Swap O(2^(k-i) * 2^i * log(2^i)) = O(2^k * i) = O(n*i)
578 In total k = log(n) iterations are performed; so in total:
579 Calls to Less O(log(n) * n)
580 Calls to Swap O(n + 2*n + 3*n + ... + (k-1)*n + k*n)
581 = O((k/2) * k * n) = O(n * k^2) = O(n * log^2(n))
584 Above results should generalize to arbitrary n = 2^k + p
585 and should not be influenced by the initial insertion sort phase:
586 Insertion sort is O(n^2) on Swap and Less, thus O(bs^2) per block of
587 size bs at n/bs blocks: O(bs*n) Swaps and Less during insertion sort.
588 Merge sort iterations start at i = log(bs). With t = log(bs) constant:
589 Calls to Less O((log(n)-t) * n + bs*n) = O(log(n)*n + (bs-t)*n)
591 Calls to Swap O(n * log^2(n) - (t^2+t)/2*n) = O(n * log^2(n))