Divide and conquer, sorting by merging from the smallest part after dividing.
Divide and conquer, similar to merge sort but with a top-down method instead of bottom-up: sorting when dividing, and splicing all together finally.
- create a min-max heap
H[0, 1, ..., n-1] - heapify from the last non-leaf node to the top
- swap top and bottom
- reduce the heap size and heapify at the top
- start from step 3
In each iteration, it distributes elements into buckets according to their radix and re-arrange their order by their radix.
- consuming one input element each repetition and growing a sorted output list
- at each iteration, removes one element from the input data, finds the location it belongs within the sorted list and inserts it there
- repeats until no input elements remain