Sorting

Sorting means arranging data into a chosen order: numbers from smallest to largest, names from A to Z, or scores from highest to lowest. The order is not fixed, because you pick the order that suits what you need to do with the data.

There are two main reasons to sort data.

• To use or present it. A quiz leaderboard is much easier to read with the highest score at the top, and a board of train departure times is only useful when it is in time order.
• To search it quickly. This is the bigger reason in computing, because searching a large data set can take a long time.

How sorting helps a search

To find a value in an unsorted list you may have to check every item, one at a time. That is a linear search, and on a long list it takes a large number of comparisons.

If the list is sorted, a binary search can be used instead. It checks the middle item, then discards the half of the list that cannot contain the value, so each comparison removes roughly half of the remaining items. Far fewer comparisons are needed, so the search finishes much sooner.

For example, imagine your class's cross-country finishing times, in minutes, are stored as 14.2, 12.8, 15.6, 11.9 and 13.4. To check whether 13.4 is in the list, a linear search would compare it with every value, because it sits at the end. Sorted, the list is 11.9, 12.8, 13.4, 14.2, 15.6, so 13.4 is the middle item and a binary search finds it with one comparison.

Sorting is therefore often done once so that many searches afterwards are cheap. The sort itself takes time, but that cost is paid back whenever the data is searched repeatedly.