Sorting Algorithms

A sorting algorithm puts every item in a list into an order you choose. It works by comparing items and moving any that are in the wrong place, repeating until nothing is left out of order. The sorted list holds exactly the same items as before — nothing is added or lost, they are just rearranged. The three standard sorts are bubble sort, merge sort and insertion sort.

There are two orders to know:

• Ascending — smallest first (12, 35, 60) or A to Z (ash, birch, cedar).
• Descending — largest first (60, 35, 12) or Z to A (cedar, birch, ash).

Numbers are sorted into numerical order; words, names and other text are sorted into alphabetical order, decided letter by letter — badger comes before beetle because both start with b, so the second letters decide it, and a comes before e. Dates and times can be sorted into chronological order too, because any one of them can be compared with another.

One algorithm, two orders

You never need a second algorithm to go the other way. Each algorithm decides where items go by comparing a pair of them, so reversing the comparison reverses the finished list. For ascending order you treat the smaller of a pair as coming first; for descending order you treat the larger as coming first. Only the comparison changes — < becomes > — while the steps, the loops and the list stay exactly the same.

Take the scores 73, 58, 91. Comparing pairs and always keeping the smaller value ahead builds 58, 73, 91; keeping the larger value ahead builds 91, 73, 58. Decide the order before you start, then apply that one rule to every comparison the algorithm makes.