19.1.1. Insertion Sort¶

What would you do if you have a stack of phone bills from the past two years and you want to order by date? A fairly natural way to handle this is to look at the first two bills and put them in order. Then take the third bill and put it into the right position with respect to the first two, and so on. As you take each bill, you would add it to the sorted pile that you have already made. This simple approach is the inspiration for insertion sort.

Insertion Sort iterates through a list of records. For each iteration, the current record is inserted in turn at the correct position within a sorted list composed of those records already processed.

Call the current record \(x\). Insertion sort will make room for \(x\) by moving other records to the right. As it does so, it will compare \(x\) with the record immediately preceding it. As soon as a record value less than or equal to \(x\) is encountered, insertion sort knows to insert \(x\) to the right of that record.

Below we show an implementation of insertion sort alongside an animation that illustrates the algorithm:

Settings

Saving...
Server Error
Resubmit

In the worst case, insertion sort requires \(O(n^2)\) time. This is because each record may need to be moved all the way to the left – think of the case where the smallest record is at the end of the list.

19.1.2. Selection Sort¶

Consider again the problem of sorting a pile of phone bills for the past year. Another intuitive approach might be to look through the pile until you find the bill for January, and pull that out. Then look through the remaining pile until you find the bill for February, and add that behind January.

Proceed through the ever-shrinking pile of bills to select the next one in order until you are done. This is the inspiration for another \(O(n^2)\) sort, called selection sort.

The \(i\)’th pass of Selection Sort “selects” the \(i\)’th smallest key in the array, placing that record in the \(i\)’th position of the array. In other words, selection sort first finds the smallest key in an unsorted list, then the next smallest, and so on.

Below we show an implementation of selection sort alongside an animation that illustrates the algorithm:

Settings

Saving...
Server Error
Resubmit

Because of the nested for loops, selection sort requires \(O(n^2)\) time.

19.1.3. Merge Sort¶

A natural approach to problem solving is divide and conquer. To use divide and conquer when sorting, we might consider breaking the list to be sorted into pieces, process the pieces, and then put them back together somehow. One way to do this would be to split the list in half, sort the halves, and then merge the sorted halves together. This is the idea behind merge sort. We give the pseudocode for the process below:

public static void mergesort(T[] values) {
   if (values.length <= 1) return; // base case, array is sorted

   else {
      // split the array into two halves and copy their contents
      left = left half of the items from values;
      right = right half of the items from values;

      // recursively sort the halves
      mergesort(left);
      mergesort(right);

      // merge the halves together and store the result in values
      merge(values, left, right);
   }
}

19.1.3.1. merge()¶

We first look at the merge operation, which takes two smaller, sorted arrays and combines them into a single larger sorted array. It begins by examining the first record of each smaller array and picks the smaller value as the smallest record overall. This smaller value is then copied into the output array. Merging continues in this way, comparing the next records of the smaller arrays and continually appending the smaller to the output array until no more input records remain:

    private void merge(T[] result, T[] a, T[] b) {
        // Index of next value to compare in a
        int left = 0;

        // Index of next value to compare in b
        int right = 0;

        // Index of next slot to fill in sorted
        int next = 0;

        // Keep comparing values in a and b until we run out of values in one
        // of the arrays
        while (left < a.length && right < b.length) {
            // Move the smaller value to sorted
            if (a[left].compareTo(b[right]) < 0) {
                result[next] = a[left];
                left++;
            } else {
                result[next] = b[right];
                right++;
            }
            next++;
        }

        // If there are values left in a, copy the rest of them to sorted
        for (; left < a.length; left++) {
            result[next] = a[left];
            next++;
        }

        // If there are values left in b, copy the rest of them to sorted
        for (; right < b.length; right++) {
            result[next] = b[right];
            next++;
        }
    }

Settings

Saving...
Server Error
Resubmit

In the worst case, the two halves of the array are of size \(n/2\), so the merge operation requires \(O(n)\) time as there are \(n\) records to be copied.

19.1.3.2. mergesort() implementation¶

Below is the complete implementation of mergesort:

Note

We use the built-in System.arraycopy() method to copy the values into the smaller left and right arrays. This is an \(O(n)\) operation!

    public void mergesort(T[] values) {
        // Base case:  values contains 0 or 1 int.  Return without
        // doing anything since values is already sorted in that case.
        if (values.length <= 1) {    
            return;
        }
        // Recursive case:  there are at least 2 values, so we need to sort them
        else {
            // Split the array into 2 equal-sized parts
            int middle = values.length / 2;
            T[] left = (T[]) (new Comparable[middle]);
            T[] right = (T[]) (new Comparable[values.length - middle]);
            System.arraycopy(values, 0, left, 0, left.length);
            System.arraycopy(values, middle, right, 0, right.length);
            
            // Recursively sort the halves
            mergesort(left);
            mergesort(right);
            
            // Merge the sorted halves together
            merge(values, left, right);
        }
    }

Settings

Saving...
Server Error
Resubmit

19.1.4. Runtime comparisons between sorting algorithms¶