zsortordered.go

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