Sorting

• Numbers to be sorted are know as keys, as they are associated with satellite data, together form a record.

Algorithms

Any comparison-based sorting algorithm requires $\Omega (n\lg n)$ comparisons and hence $\Omega (n\lg n)$ time.

• insertion-sort
• merge-sort
• heapsort
• quicksort