Samplesort

This product was added to computer science because of the content, defects on the quality assurance side of the editor. This is done to bring the quality of the articles from the computer science subject area to an acceptable level. Help us to eliminate the substantive shortcomings of this article and take part you in the discussion! ( )

Samplesort is a sorting algorithm in 1970 by WD Frazer and AC McKellar in scientific publication Samplesort: published A Sampling Approach to Minimal Storage Tree Sorting. This algorithm sorts a command recursively by choosing at each step a random selection (samples) of elements from the unsorted input sequence, of which a subset is used as separators, which in turn split the input sequence for the next recursive sorting steps. By oversampling, ie the selection of more separators as necessary and choosing the best ( most uniform ones) from a division of the input sequence in (on average) is quite the same reach large pieces, which increases the quality of this divide-and -conquer approach.

Principle

In the method is a generalization of the minimum quicksort approach. For a better understanding of the process can be divided in three separate stages. However, this separation can not be maintained in an implementation with objective of minimum memory requirements. In the first stage a random sub-sequence is selected from the input sequence.