src/slices/zsortanyfunc.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 // insertionSortCmpFunc sorts data[a:b] using insertion sort.
  10 func insertionSortCmpFunc[E any](data []E, a, b int, cmp func(a, b E) int) {
  11         for i := a + 1; i < b; i++ {
  12                 for j := i; j > a && (cmp(data[j], data[j-1]) < 0); j-- {
  13                         data[j], data[j-1] = data[j-1], data[j]
  14                 }
  15         }
  16 }
  17
  18 // siftDownCmpFunc 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 siftDownCmpFunc[E any](data []E, lo, hi, first int, cmp func(a, b E) int) {
  21         root := lo
  22         for {
  23                 child := 2*root + 1
  24                 if child >= hi {
  25                         break
  26                 }
  27                 if child+1 < hi && (cmp(data[first+child], data[first+child+1]) < 0) {
  28                         child++
  29                 }
  30                 if !(cmp(data[first+root], data[first+child]) < 0) {
  31                         return
  32                 }
  33                 data[first+root], data[first+child] = data[first+child], data[first+root]
  34                 root = child
  35         }
  36 }
  37
  38 func heapSortCmpFunc[E any](data []E, a, b int, cmp func(a, b E) 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                 siftDownCmpFunc(data, i, hi, first, cmp)
  46         }
  47
  48         // Pop elements, largest first, into end of data.
  49         for i := hi - 1; i >= 0; i-- {
  50                 data[first], data[first+i] = data[first+i], data[first]
  51                 siftDownCmpFunc(data, lo, i, first, cmp)
  52         }
  53 }
  54
  55 // pdqsortCmpFunc 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 pdqsortCmpFunc[E any](data []E, a, b, limit int, cmp func(a, b E) 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                         insertionSortCmpFunc(data, a, b, cmp)
  74                         return
  75                 }
  76
  77                 // Fall back to heapsort if too many bad choices were made.
  78                 if limit == 0 {
  79                         heapSortCmpFunc(data, a, b, cmp)
  80                         return
  81                 }
  82
  83                 // If the last partitioning was imbalanced, we need to breaking patterns.
  84                 if !wasBalanced {
  85                         breakPatternsCmpFunc(data, a, b, cmp)
  86                         limit--
  87                 }
  88
  89                 pivot, hint := choosePivotCmpFunc(data, a, b, cmp)
  90                 if hint == decreasingHint {
  91                         reverseRangeCmpFunc(data, a, b, cmp)
  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 partialInsertionSortCmpFunc(data, a, b, cmp) {
 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 && !(cmp(data[a-1], data[pivot]) < 0) {
 109                         mid := partitionEqualCmpFunc(data, a, b, pivot, cmp)
 110                         a = mid
 111                         continue
 112                 }
 113
 114                 mid, alreadyPartitioned := partitionCmpFunc(data, a, b, pivot, cmp)
 115                 wasPartitioned = alreadyPartitioned
 116
 117                 leftLen, rightLen := mid-a, b-mid
 118                 balanceThreshold := length / 8
 119                 if leftLen < rightLen {
 120                         wasBalanced = leftLen >= balanceThreshold
 121                         pdqsortCmpFunc(data, a, mid, limit, cmp)
 122                         a = mid + 1
 123                 } else {
 124                         wasBalanced = rightLen >= balanceThreshold
 125                         pdqsortCmpFunc(data, mid+1, b, limit, cmp)
 126                         b = mid
 127                 }
 128         }
 129 }
 130
 131 // partitionCmpFunc 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 partitionCmpFunc[E any](data []E, a, b, pivot int, cmp func(a, b E) int) (newpivot int, alreadyPartitioned bool) {
 136         data[a], data[pivot] = data[pivot], data[a]
 137         i, j := a+1, b-1 // i and j are inclusive of the elements remaining to be partitioned
 138
 139         for i <= j && (cmp(data[i], data[a]) < 0) {
 140                 i++
 141         }
 142         for i <= j && !(cmp(data[j], data[a]) < 0) {
 143                 j--
 144         }
 145         if i > j {
 146                 data[j], data[a] = data[a], data[j]
 147                 return j, true
 148         }
 149         data[i], data[j] = data[j], data[i]
 150         i++
 151         j--
 152
 153         for {
 154                 for i <= j && (cmp(data[i], data[a]) < 0) {
 155                         i++
 156                 }
 157                 for i <= j && !(cmp(data[j], data[a]) < 0) {
 158                         j--
 159                 }
 160                 if i > j {
 161                         break
 162                 }
 163                 data[i], data[j] = data[j], data[i]
 164                 i++
 165                 j--
 166         }
 167         data[j], data[a] = data[a], data[j]
 168         return j, false
 169 }
 170
 171 // partitionEqualCmpFunc 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 partitionEqualCmpFunc[E any](data []E, a, b, pivot int, cmp func(a, b E) int) (newpivot int) {
 174         data[a], data[pivot] = data[pivot], data[a]
 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 && !(cmp(data[a], data[i]) < 0) {
 179                         i++
 180                 }
 181                 for i <= j && (cmp(data[a], data[j]) < 0) {
 182                         j--
 183                 }
 184                 if i > j {
 185                         break
 186                 }
 187                 data[i], data[j] = data[j], data[i]
 188                 i++
 189                 j--
 190         }
 191         return i
 192 }
 193
 194 // partialInsertionSortCmpFunc partially sorts a slice, returns true if the slice is sorted at the end.
 195 func partialInsertionSortCmpFunc[E any](data []E, a, b int, cmp func(a, b E) 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 && !(cmp(data[i], data[i-1]) < 0) {
 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[i], data[i-1] = data[i-1], data[i]
 215
 216                 // Shift the smaller one to the left.
 217                 if i-a >= 2 {
 218                         for j := i - 1; j >= 1; j-- {
 219                                 if !(cmp(data[j], data[j-1]) < 0) {
 220                                         break
 221                                 }
 222                                 data[j], data[j-1] = data[j-1], data[j]
 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 !(cmp(data[j], data[j-1]) < 0) {
 229                                         break
 230                                 }
 231                                 data[j], data[j-1] = data[j-1], data[j]
 232                         }
 233                 }
 234         }
 235         return false
 236 }
 237
 238 // breakPatternsCmpFunc scatters some elements around in an attempt to break some patterns
 239 // that might cause imbalanced partitions in quicksort.
 240 func breakPatternsCmpFunc[E any](data []E, a, b int, cmp func(a, b E) 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[idx], data[a+other] = data[a+other], data[idx]
 252                 }
 253         }
 254 }
 255
 256 // choosePivotCmpFunc 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 choosePivotCmpFunc[E any](data []E, a, b int, cmp func(a, b E) 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 = medianAdjacentCmpFunc(data, i, &swaps, cmp)
 280                         j = medianAdjacentCmpFunc(data, j, &swaps, cmp)
 281                         k = medianAdjacentCmpFunc(data, k, &swaps, cmp)
 282                 }
 283                 // Find the median among i, j, k and stores it into j.
 284                 j = medianCmpFunc(data, i, j, k, &swaps, cmp)
 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 // order2CmpFunc returns x,y where data[x] <= data[y], where x,y=a,b or x,y=b,a.
 298 func order2CmpFunc[E any](data []E, a, b int, swaps *int, cmp func(a, b E) int) (int, int) {
 299         if cmp(data[b], data[a]) < 0 {
 300                 *swaps++
 301                 return b, a
 302         }
 303         return a, b
 304 }
 305
 306 // medianCmpFunc returns x where data[x] is the median of data[a],data[b],data[c], where x is a, b, or c.
 307 func medianCmpFunc[E any](data []E, a, b, c int, swaps *int, cmp func(a, b E) int) int {
 308         a, b = order2CmpFunc(data, a, b, swaps, cmp)
 309         b, c = order2CmpFunc(data, b, c, swaps, cmp)
 310         a, b = order2CmpFunc(data, a, b, swaps, cmp)
 311         return b
 312 }
 313
 314 // medianAdjacentCmpFunc finds the median of data[a - 1], data[a], data[a + 1] and stores the index into a.
 315 func medianAdjacentCmpFunc[E any](data []E, a int, swaps *int, cmp func(a, b E) int) int {
 316         return medianCmpFunc(data, a-1, a, a+1, swaps, cmp)
 317 }
 318
 319 func reverseRangeCmpFunc[E any](data []E, a, b int, cmp func(a, b E) int) {
 320         i := a
 321         j := b - 1
 322         for i < j {
 323                 data[i], data[j] = data[j], data[i]
 324                 i++
 325                 j--
 326         }
 327 }
 328
 329 func swapRangeCmpFunc[E any](data []E, a, b, n int, cmp func(a, b E) int) {
 330         for i := 0; i < n; i++ {
 331                 data[a+i], data[b+i] = data[b+i], data[a+i]
 332         }
 333 }
 334
 335 func stableCmpFunc[E any](data []E, n int, cmp func(a, b E) int) {
 336         blockSize := 20 // must be > 0
 337         a, b := 0, blockSize
 338         for b <= n {
 339                 insertionSortCmpFunc(data, a, b, cmp)
 340                 a = b
 341                 b += blockSize
 342         }
 343         insertionSortCmpFunc(data, a, n, cmp)
 344
 345         for blockSize < n {
 346                 a, b = 0, 2*blockSize
 347                 for b <= n {
 348                         symMergeCmpFunc(data, a, a+blockSize, b, cmp)
 349                         a = b
 350                         b += 2 * blockSize
 351                 }
 352                 if m := a + blockSize; m < n {
 353                         symMergeCmpFunc(data, a, m, n, cmp)
 354                 }
 355                 blockSize *= 2
 356         }
 357 }
 358
 359 // symMergeCmpFunc 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 symMergeCmpFunc[E any](data []E, a, m, b int, cmp func(a, b E) 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 cmp(data[h], data[a]) < 0 {
 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[k], data[k+1] = data[k+1], data[k]
 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 !(cmp(data[m], data[h]) < 0) {
 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[k], data[k-1] = data[k-1], data[k]
 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 !(cmp(data[p-c], data[c]) < 0) {
 442                         start = c + 1
 443                 } else {
 444                         r = c
 445                 }
 446         }
 447
 448         end := n - start
 449         if start < m && m < end {
 450                 rotateCmpFunc(data, start, m, end, cmp)
 451         }
 452         if a < start && start < mid {
 453                 symMergeCmpFunc(data, a, start, mid, cmp)
 454         }
 455         if mid < end && end < b {
 456                 symMergeCmpFunc(data, mid, end, b, cmp)
 457         }
 458 }
 459
 460 // rotateCmpFunc 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 rotateCmpFunc[E any](data []E, a, m, b int, cmp func(a, b E) int) {
 465         i := m - a
 466         j := b - m
 467
 468         for i != j {
 469                 if i > j {
 470                         swapRangeCmpFunc(data, m-i, m, j, cmp)
 471                         i -= j
 472                 } else {
 473                         swapRangeCmpFunc(data, m-i, m+j-i, i, cmp)
 474                         j -= i
 475                 }
 476         }
 477         // i == j
 478         swapRangeCmpFunc(data, m-i, m, i, cmp)
 479 }