Proportion extend sort
Proportion extend sort (abbreviated as PESort) is an in-place, comparison-based sorting algorithm which attempts to improve on the performance, particularly the worst-case performance, of quicksort.

The basic partitioning operation in quicksort has a linear access pattern which is extremely efficient on modern memory hierarchies, but the performance of the algorithm is critically dependent on the choice of a pivot value. A good pivot will divide the data to be sorted into nearly-equal halves. A poor choice will result in a grossly lopsided division, leaving one part almost as large as the original problem and causing performance.

Proportion extend sort begins with a sorted prefix of elements, then uses the median of that sample to partition the following elements. By bounding the size ratio between the sample and the data being partitioned (i.e. the proportion by which the sorted prefix is extended), the imbalance is limited. In this, it has some similarities to samplesort.
Q181593
sorting algorithm
Concept
Q186094
worst-case performance
Concept
Q486598
quicksort
Concept
Q1589327
memory hierarchies
Concept
Q182425
samplesort
Concept
Q104843517
Proportion extend sort
UNK
Q104843517
Proportion extend sort
UNK
instance of