Why is sorting is important?

Answer 1

Sorting algorithms are important because searching for data is more efficient when the data is in sorted order. For instance, if we have data that can be sorted by a key value, we can locate the data associated with a key much more quickly if we start in the middle. If the key is there then we're done, otherwise we compare the keys to determine which half of the data contains our key, and disregard the other half completely. We then repeat the process with the remaining half, reducing the number of elements we need to search by half each time. Eventually, we will either find our key or there will be no elements left to search, in which case the key does not exist. This is much quicker than searching every element from first to last. In terms of complexity, the latter takes O(n) time to determine that a key does not exist (the worst case), whereas the former would take O(log n) time, which is substantially faster.

Sorting algorithms are also important because they teach us how to write efficient algorithms. Humans are creatures of habit and when tasked with sorting things we usually use the same simple methods. For instance, for a small set of data we might take the first two elements and sort them, then insert the third in its proper place, then the fourth, and so on. This technique approximates the insertion sort algorithm. For larger sets we might choose to divide the set into smaller sets, sort each of them individually, then repeatedly examine the top elements, taking the smallest each time and placing it in a new set. This is fairly similar to the merge algorithm. By expressing these actions as an algorithm we can test them to determine which is the most efficient.

We also have to take into account the stability of the algorithm. A stable sort keeps equal items in the same order they were input. This requirement may make the algorithm less efficient. Similarly, we must take into account whether the algorithm can be executed in place or whether auxiliary memory is required. An in place sort uses memory more efficiently but may sacrifice performance. This can be important when sorting disk-based arrays that are too large to fit into memory. Moving data around in memory is easier to achieve than moving data around on disk, thus it is often necessary to sacrifice disk space to maintain performance.