Hybrid variety

Hybridsort is a special sorting process that combines the properties of Bucketsort with other sorting processes such as Heapsort or Quicksort . The keys to be sorted are divided according to the bucket sort principle. The elements pre-sorted in this way are then finally sorted using the Heapsort algorithm. The sorted buckets are then joined together.

requirement

Similar to Bucketsort, the number of values ​​the sort keys can accept must be finite.

principle

The elements of a list are distributed over a finite number of buckets according to their key properties. The keys are normalized to the interval using the maximum key . The limits in this interval are defined by the number of baskets . The elements are then distributed to the baskets using the following formula: ${\displaystyle {\text{max}}}$ ${\displaystyle [0;1]}$ ${\displaystyle a}$

${\displaystyle {\text{Index}}_{\text{Korb}}={\frac {\text{Schlüssel}}{\text{max}}}\cdot a}$

The keys distributed in this way are sorted within the baskets with Heapsort.

The pre-sorted and sorted baskets deliver the sorted list in a row.

complexity

Assuming that x _{i is} independent and evenly distributed, a running time of up results in both the best and the average case of the method . In the general case, however, the runtime is significantly worse. The worst case is dominated by the runtime of Heapsort and is therefore . ${\displaystyle {\mathcal {O}}(n)}$ ${\displaystyle {\mathcal {O}}(n\cdot \log n)}$

literature

• Torben Hagerup: Hybridsort revisited and parallelized . In: Information Processing Letters . tape 32 , no. 1 , 1989, pp. 35-39 , doi : 10.1016 / 0020-0190 (89) 90066-5 .
• Henk Meijer and Selim G. Akl: The design and analysis of a new hybrid sorting algorithm . In: Information Processing Letters . tape 10 , no. 4,5 , 1980, pp. 213-218 , doi : 10.1016 / 0020-0190 (80) 90143-X .