Proportion extend sort

Uses your system voice; voice and rate in settings.

Snapshot

≈ 2 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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.

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.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1359732962 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001359732962 · captured 1781640518.0 · version history

Cite this page as: encyclopegia.org, “Proportion extend sort”, snapshot enwiki-001359732962. https://encyclopegia.org/a/proportion-extend-sort

Sources cited in this revision

Extracted from the cited revision's reference blocks; absent citations are not invented.