SUMMARY

Sorting algorithms are selected using criteria such as memory use and stability as well as best, average, and worst-case performance. No comparison sort can have better worst-case performance than O(n log(n)).

Selection sort is one of the simplest sorting algorithms, but it is O(n²) in all cases. It requires only O(n) swaps, however, so it may be suitable for data sets where copying is very expensive. Insertion sort is efficient when dealing with mostly sorted data sets, where it can have O(n) performance, but average and worst cases are O(n²). Quicksort is a divide-and-conquer algorithm that offers O(n log(n)) performance in the best and average cases and O(n²) in the worst case. Merge sort is another divide-and-conquer algorithm that offers O(n log(n)) performance in all cases. It is especially useful for sorting data sets that cannot fit into memory. You can make any sorting algorithm stable by assigning a sequence number to each element and using the sequence number as the...