Appendix - Sorting Algorithms

What is Sort Key?

Sometimes we sort scalar objects such as numbers, and other times we might want to sort non-scalar objects such as Objects with many class variables. In the latter case, one must designate a specific variable (or a function) to be used as the sort key. A sort key is part of the data item that determines the ordering relation used in the sort. (In Java, this is achieved by using the Comparable interface.)

What are Interval vs External Sorting Algorithms?

Sometimes the data to be sorted is so large that it cannot fit in memory. The sorting algorithms in this case have very different requirements, since only a fraction of the data can be examined at a time. Algorithms that sort data that cannot all be stored in memory are called external sorting algorithms. Those that sort data that can fit entirely in memory are called internal sorts.

What are Stable Sorting Algorithms?

Sometimes the data to be sorted does not have unique keys and multiple elements can have the same key. It may be important for a sorting algorithm to preserve the relative order of elements with equal keys. Sorts that preserve the order of equal keys are called stable sorts. To give an example, suppose that data is sorted by last name, and if there are any elements with equal last names, then ties are broken by sorting by first name. One way to do this is to first sort all of the data by first name. Then, the data can be sorted by last name, as long as it has the property that elements with equal keys stay in the same relative order. This will work because if there are two people with the same last name but different first names, then the second sort will move elements with different last names relative to each other, but those with equal last names will stay in the same relative order, and since they are already sorted by first name, those with smaller first names and equal last names will precede those with larger first names and equal last names. E.g.,

zachary abigail
smith harry
jones mary
smith sam

becomes,

jones mary
smith harry 
smith sam
zachary abigail

What are Natural Sorting Algorithms?

When data is sorted, mostly what takes place is that keys are compared and data items are moved around. When measuring the performance of sorting algorithms, sometimes it is only the number of key comparisons that are of interest. However, if the data items are very big, then moving a data item can be a costly operation. In this case we may also be interested in how many data movement operations take place as a function of input size. The number of key comparisons might be small but if the data movements are frequent, then it may not perform as well as an algorithm with fewer data movements and more key comparisons. One measure of a sort is how much data movement it performs when the initial data set is already sorted. Sorts that do not move the data much in that case are called natural sorts.