Sorting

Sorting is the process of arranging a set of data elements in ascending or descending order by a key, and it is one of the oldest and most widely applied problems in computer science. Database indexes, search result pages, leaderboards, and parcel sorting all rest on it. The chapter works through the five families of sorting algorithms — insertion, exchange, selection, merge, and radix — because each family attacks the problem differently: insertion and selection grow an ordered prefix one element at a time, exchange swaps pairs into place, merge exploits an already-sorted run, and radix sorts on individual digits instead of comparing whole keys. Alongside the algorithms themselves, the chapter keeps returning to three questions that decide whether a sort is any good in practice: how much time it takes, how much extra space it needs, and whether it is stable, meaning that equal elements keep their relative order. By the end you will be able to write the core loop of each algorithm, state its time and space complexity, explain which data distribution it suits, and choose an algorithm for a given dataset rather than reaching for the one you happen to remember best.