Pattern-defeating Quicksort

标签：Pattern Quicksort mid defeating pdqsort limit func pivot data

https://arxiv.org/pdf/2106.05123.pdf

// pdqsort_func sorts data[a:b]. // The algorithm based on pattern-defeating quicksort(pdqsort), but without the optimizations from BlockQuicksort. // pdqsort paper: https://arxiv.org/pdf/2106.05123.pdf // C++ implementation: https://github.com/orlp/pdqsort // Rust implementation: https://docs.rs/pdqsort/latest/pdqsort/ // limit is the number of allowed bad (very unbalanced) pivots before falling back to heapsort. func pdqsort_func(data lessSwap, a, b, limit int) {     const maxInsertion = 12
    var (         wasBalanced    = true // whether the last partitioning was reasonably balanced         wasPartitioned = true // whether the slice was already partitioned     )
    for {         length := b - a
        if length <= maxInsertion {             insertionSort_func(data, a, b)             return         }
        // Fall back to heapsort if too many bad choices were made.         if limit == 0 {             heapSort_func(data, a, b)             return         }
        // If the last partitioning was imbalanced, we need to breaking patterns.         if !wasBalanced {             breakPatterns_func(data, a, b)             limit--         }
        pivot, hint := choosePivot_func(data, a, b)         if hint == decreasingHint {             reverseRange_func(data, a, b)             // The chosen pivot was pivot-a elements after the start of the array.             // After reversing it is pivot-a elements before the end of the array.             // The idea came from Rust's implementation.             pivot = (b - 1) - (pivot - a)             hint = increasingHint         }
        // The slice is likely already sorted.         if wasBalanced && wasPartitioned && hint == increasingHint {             if partialInsertionSort_func(data, a, b) {                 return             }         }
        // Probably the slice contains many duplicate elements, partition the slice into         // elements equal to and elements greater than the pivot.         if a > 0 && !data.Less(a-1, pivot) {             mid := partitionEqual_func(data, a, b, pivot)             a = mid             continue         }
        mid, alreadyPartitioned := partition_func(data, a, b, pivot)         wasPartitioned = alreadyPartitioned
        leftLen, rightLen := mid-a, b-mid         balanceThreshold := length / 8         if leftLen < rightLen {             wasBalanced = leftLen >= balanceThreshold             pdqsort_func(data, a, mid, limit)             a = mid + 1         } else {             wasBalanced = rightLen >= balanceThreshold             pdqsort_func(data, mid+1, b, limit)             b = mid         }     } }

 

标签：Pattern,Quicksort,mid,defeating,pdqsort,limit,func,pivot,data
From： https://www.cnblogs.com/rsapaper/p/16939304.html