Source file src/sort/zsortinterface.go

```     1  // Code generated by gen_sort_variants.go; DO NOT EDIT.
2
4  // Use of this source code is governed by a BSD-style
6
7  package sort
8
9  // insertionSort sorts data[a:b] using insertion sort.
10  func insertionSort(data Interface, a, b int) {
11  	for i := a + 1; i < b; i++ {
12  		for j := i; j > a && data.Less(j, j-1); j-- {
13  			data.Swap(j, j-1)
14  		}
15  	}
16  }
17
18  // siftDown implements the heap property on data[lo:hi].
19  // first is an offset into the array where the root of the heap lies.
20  func siftDown(data Interface, lo, hi, first int) {
21  	root := lo
22  	for {
23  		child := 2*root + 1
24  		if child >= hi {
25  			break
26  		}
27  		if child+1 < hi && data.Less(first+child, first+child+1) {
28  			child++
29  		}
30  		if !data.Less(first+root, first+child) {
31  			return
32  		}
33  		data.Swap(first+root, first+child)
34  		root = child
35  	}
36  }
37
38  func heapSort(data Interface, a, b int) {
39  	first := a
40  	lo := 0
41  	hi := b - a
42
43  	// Build heap with greatest element at top.
44  	for i := (hi - 1) / 2; i >= 0; i-- {
45  		siftDown(data, i, hi, first)
46  	}
47
48  	// Pop elements, largest first, into end of data.
49  	for i := hi - 1; i >= 0; i-- {
50  		data.Swap(first, first+i)
51  		siftDown(data, lo, i, first)
52  	}
53  }
54
55  // pdqsort sorts data[a:b].
56  // The algorithm based on pattern-defeating quicksort(pdqsort), but without the optimizations from BlockQuicksort.
57  // pdqsort paper: https://arxiv.org/pdf/2106.05123.pdf
58  // C++ implementation: https://github.com/orlp/pdqsort
59  // Rust implementation: https://docs.rs/pdqsort/latest/pdqsort/
60  // limit is the number of allowed bad (very unbalanced) pivots before falling back to heapsort.
61  func pdqsort(data Interface, a, b, limit int) {
62  	const maxInsertion = 12
63
64  	var (
65  		wasBalanced    = true // whether the last partitioning was reasonably balanced
66  		wasPartitioned = true // whether the slice was already partitioned
67  	)
68
69  	for {
70  		length := b - a
71
72  		if length <= maxInsertion {
73  			insertionSort(data, a, b)
74  			return
75  		}
76
77  		// Fall back to heapsort if too many bad choices were made.
78  		if limit == 0 {
79  			heapSort(data, a, b)
80  			return
81  		}
82
83  		// If the last partitioning was imbalanced, we need to breaking patterns.
84  		if !wasBalanced {
85  			breakPatterns(data, a, b)
86  			limit--
87  		}
88
89  		pivot, hint := choosePivot(data, a, b)
90  		if hint == decreasingHint {
91  			reverseRange(data, a, b)
92  			// The chosen pivot was pivot-a elements after the start of the array.
93  			// After reversing it is pivot-a elements before the end of the array.
94  			// The idea came from Rust's implementation.
95  			pivot = (b - 1) - (pivot - a)
96  			hint = increasingHint
97  		}
98
99  		// The slice is likely already sorted.
100  		if wasBalanced && wasPartitioned && hint == increasingHint {
101  			if partialInsertionSort(data, a, b) {
102  				return
103  			}
104  		}
105
106  		// Probably the slice contains many duplicate elements, partition the slice into
107  		// elements equal to and elements greater than the pivot.
108  		if a > 0 && !data.Less(a-1, pivot) {
109  			mid := partitionEqual(data, a, b, pivot)
110  			a = mid
111  			continue
112  		}
113
114  		mid, alreadyPartitioned := partition(data, a, b, pivot)
116
117  		leftLen, rightLen := mid-a, b-mid
118  		balanceThreshold := length / 8
119  		if leftLen < rightLen {
120  			wasBalanced = leftLen >= balanceThreshold
121  			pdqsort(data, a, mid, limit)
122  			a = mid + 1
123  		} else {
124  			wasBalanced = rightLen >= balanceThreshold
125  			pdqsort(data, mid+1, b, limit)
126  			b = mid
127  		}
128  	}
129  }
130
131  // partition does one quicksort partition.
132  // Let p = data[pivot]
133  // Moves elements in data[a:b] around, so that data[i]<p and data[j]>=p for i<newpivot and j>newpivot.
134  // On return, data[newpivot] = p
135  func partition(data Interface, a, b, pivot int) (newpivot int, alreadyPartitioned bool) {
136  	data.Swap(a, pivot)
137  	i, j := a+1, b-1 // i and j are inclusive of the elements remaining to be partitioned
138
139  	for i <= j && data.Less(i, a) {
140  		i++
141  	}
142  	for i <= j && !data.Less(j, a) {
143  		j--
144  	}
145  	if i > j {
146  		data.Swap(j, a)
147  		return j, true
148  	}
149  	data.Swap(i, j)
150  	i++
151  	j--
152
153  	for {
154  		for i <= j && data.Less(i, a) {
155  			i++
156  		}
157  		for i <= j && !data.Less(j, a) {
158  			j--
159  		}
160  		if i > j {
161  			break
162  		}
163  		data.Swap(i, j)
164  		i++
165  		j--
166  	}
167  	data.Swap(j, a)
168  	return j, false
169  }
170
171  // partitionEqual partitions data[a:b] into elements equal to data[pivot] followed by elements greater than data[pivot].
172  // It assumed that data[a:b] does not contain elements smaller than the data[pivot].
173  func partitionEqual(data Interface, a, b, pivot int) (newpivot int) {
174  	data.Swap(a, pivot)
175  	i, j := a+1, b-1 // i and j are inclusive of the elements remaining to be partitioned
176
177  	for {
178  		for i <= j && !data.Less(a, i) {
179  			i++
180  		}
181  		for i <= j && data.Less(a, j) {
182  			j--
183  		}
184  		if i > j {
185  			break
186  		}
187  		data.Swap(i, j)
188  		i++
189  		j--
190  	}
191  	return i
192  }
193
194  // partialInsertionSort partially sorts a slice, returns true if the slice is sorted at the end.
195  func partialInsertionSort(data Interface, a, b int) bool {
196  	const (
197  		maxSteps         = 5  // maximum number of adjacent out-of-order pairs that will get shifted
198  		shortestShifting = 50 // don't shift any elements on short arrays
199  	)
200  	i := a + 1
201  	for j := 0; j < maxSteps; j++ {
202  		for i < b && !data.Less(i, i-1) {
203  			i++
204  		}
205
206  		if i == b {
207  			return true
208  		}
209
210  		if b-a < shortestShifting {
211  			return false
212  		}
213
214  		data.Swap(i, i-1)
215
216  		// Shift the smaller one to the left.
217  		if i-a >= 2 {
218  			for j := i - 1; j >= 1; j-- {
219  				if !data.Less(j, j-1) {
220  					break
221  				}
222  				data.Swap(j, j-1)
223  			}
224  		}
225  		// Shift the greater one to the right.
226  		if b-i >= 2 {
227  			for j := i + 1; j < b; j++ {
228  				if !data.Less(j, j-1) {
229  					break
230  				}
231  				data.Swap(j, j-1)
232  			}
233  		}
234  	}
235  	return false
236  }
237
238  // breakPatterns scatters some elements around in an attempt to break some patterns
239  // that might cause imbalanced partitions in quicksort.
240  func breakPatterns(data Interface, a, b int) {
241  	length := b - a
242  	if length >= 8 {
243  		random := xorshift(length)
244  		modulus := nextPowerOfTwo(length)
245
246  		for idx := a + (length/4)*2 - 1; idx <= a+(length/4)*2+1; idx++ {
247  			other := int(uint(random.Next()) & (modulus - 1))
248  			if other >= length {
249  				other -= length
250  			}
251  			data.Swap(idx, a+other)
252  		}
253  	}
254  }
255
256  // choosePivot chooses a pivot in data[a:b].
257  //
258  // [0,8): chooses a static pivot.
259  // [8,shortestNinther): uses the simple median-of-three method.
260  // [shortestNinther,∞): uses the Tukey ninther method.
261  func choosePivot(data Interface, a, b int) (pivot int, hint sortedHint) {
262  	const (
263  		shortestNinther = 50
264  		maxSwaps        = 4 * 3
265  	)
266
267  	l := b - a
268
269  	var (
270  		swaps int
271  		i     = a + l/4*1
272  		j     = a + l/4*2
273  		k     = a + l/4*3
274  	)
275
276  	if l >= 8 {
277  		if l >= shortestNinther {
278  			// Tukey ninther method, the idea came from Rust's implementation.
279  			i = medianAdjacent(data, i, &swaps)
280  			j = medianAdjacent(data, j, &swaps)
281  			k = medianAdjacent(data, k, &swaps)
282  		}
283  		// Find the median among i, j, k and stores it into j.
284  		j = median(data, i, j, k, &swaps)
285  	}
286
287  	switch swaps {
288  	case 0:
289  		return j, increasingHint
290  	case maxSwaps:
291  		return j, decreasingHint
292  	default:
293  		return j, unknownHint
294  	}
295  }
296
297  // order2 returns x,y where data[x] <= data[y], where x,y=a,b or x,y=b,a.
298  func order2(data Interface, a, b int, swaps *int) (int, int) {
299  	if data.Less(b, a) {
300  		*swaps++
301  		return b, a
302  	}
303  	return a, b
304  }
305
306  // median returns x where data[x] is the median of data[a],data[b],data[c], where x is a, b, or c.
307  func median(data Interface, a, b, c int, swaps *int) int {
308  	a, b = order2(data, a, b, swaps)
309  	b, c = order2(data, b, c, swaps)
310  	a, b = order2(data, a, b, swaps)
311  	return b
312  }
313
314  // medianAdjacent finds the median of data[a - 1], data[a], data[a + 1] and stores the index into a.
315  func medianAdjacent(data Interface, a int, swaps *int) int {
316  	return median(data, a-1, a, a+1, swaps)
317  }
318
319  func reverseRange(data Interface, a, b int) {
320  	i := a
321  	j := b - 1
322  	for i < j {
323  		data.Swap(i, j)
324  		i++
325  		j--
326  	}
327  }
328
329  func swapRange(data Interface, a, b, n int) {
330  	for i := 0; i < n; i++ {
331  		data.Swap(a+i, b+i)
332  	}
333  }
334
335  func stable(data Interface, n int) {
336  	blockSize := 20 // must be > 0
337  	a, b := 0, blockSize
338  	for b <= n {
339  		insertionSort(data, a, b)
340  		a = b
341  		b += blockSize
342  	}
343  	insertionSort(data, a, n)
344
345  	for blockSize < n {
346  		a, b = 0, 2*blockSize
347  		for b <= n {
348  			symMerge(data, a, a+blockSize, b)
349  			a = b
350  			b += 2 * blockSize
351  		}
352  		if m := a + blockSize; m < n {
353  			symMerge(data, a, m, n)
354  		}
355  		blockSize *= 2
356  	}
357  }
358
359  // symMerge merges the two sorted subsequences data[a:m] and data[m:b] using
360  // the SymMerge algorithm from Pok-Son Kim and Arne Kutzner, "Stable Minimum
361  // Storage Merging by Symmetric Comparisons", in Susanne Albers and Tomasz
362  // Radzik, editors, Algorithms - ESA 2004, volume 3221 of Lecture Notes in
363  // Computer Science, pages 714-723. Springer, 2004.
364  //
365  // Let M = m-a and N = b-n. Wolog M < N.
366  // The recursion depth is bound by ceil(log(N+M)).
367  // The algorithm needs O(M*log(N/M + 1)) calls to data.Less.
368  // The algorithm needs O((M+N)*log(M)) calls to data.Swap.
369  //
370  // The paper gives O((M+N)*log(M)) as the number of assignments assuming a
371  // rotation algorithm which uses O(M+N+gcd(M+N)) assignments. The argumentation
372  // in the paper carries through for Swap operations, especially as the block
373  // swapping rotate uses only O(M+N) Swaps.
374  //
375  // symMerge assumes non-degenerate arguments: a < m && m < b.
376  // Having the caller check this condition eliminates many leaf recursion calls,
377  // which improves performance.
378  func symMerge(data Interface, a, m, b int) {
379  	// Avoid unnecessary recursions of symMerge
380  	// by direct insertion of data[a] into data[m:b]
381  	// if data[a:m] only contains one element.
382  	if m-a == 1 {
383  		// Use binary search to find the lowest index i
384  		// such that data[i] >= data[a] for m <= i < b.
385  		// Exit the search loop with i == b in case no such index exists.
386  		i := m
387  		j := b
388  		for i < j {
389  			h := int(uint(i+j) >> 1)
390  			if data.Less(h, a) {
391  				i = h + 1
392  			} else {
393  				j = h
394  			}
395  		}
396  		// Swap values until data[a] reaches the position before i.
397  		for k := a; k < i-1; k++ {
398  			data.Swap(k, k+1)
399  		}
400  		return
401  	}
402
403  	// Avoid unnecessary recursions of symMerge
404  	// by direct insertion of data[m] into data[a:m]
405  	// if data[m:b] only contains one element.
406  	if b-m == 1 {
407  		// Use binary search to find the lowest index i
408  		// such that data[i] > data[m] for a <= i < m.
409  		// Exit the search loop with i == m in case no such index exists.
410  		i := a
411  		j := m
412  		for i < j {
413  			h := int(uint(i+j) >> 1)
414  			if !data.Less(m, h) {
415  				i = h + 1
416  			} else {
417  				j = h
418  			}
419  		}
420  		// Swap values until data[m] reaches the position i.
421  		for k := m; k > i; k-- {
422  			data.Swap(k, k-1)
423  		}
424  		return
425  	}
426
427  	mid := int(uint(a+b) >> 1)
428  	n := mid + m
429  	var start, r int
430  	if m > mid {
431  		start = n - b
432  		r = mid
433  	} else {
434  		start = a
435  		r = m
436  	}
437  	p := n - 1
438
439  	for start < r {
440  		c := int(uint(start+r) >> 1)
441  		if !data.Less(p-c, c) {
442  			start = c + 1
443  		} else {
444  			r = c
445  		}
446  	}
447
448  	end := n - start
449  	if start < m && m < end {
450  		rotate(data, start, m, end)
451  	}
452  	if a < start && start < mid {
453  		symMerge(data, a, start, mid)
454  	}
455  	if mid < end && end < b {
456  		symMerge(data, mid, end, b)
457  	}
458  }
459
460  // rotate rotates two consecutive blocks u = data[a:m] and v = data[m:b] in data:
461  // Data of the form 'x u v y' is changed to 'x v u y'.
462  // rotate performs at most b-a many calls to data.Swap,
463  // and it assumes non-degenerate arguments: a < m && m < b.
464  func rotate(data Interface, a, m, b int) {
465  	i := m - a
466  	j := b - m
467
468  	for i != j {
469  		if i > j {
470  			swapRange(data, m-i, m, j)
471  			i -= j
472  		} else {
473  			swapRange(data, m-i, m+j-i, i)
474  			j -= i
475  		}
476  	}
477  	// i == j
478  	swapRange(data, m-i, m, i)
479  }
480
```

View as plain text