I am currently reviewing sort methods in the Coursera/Princeton Algorithms, Part 1 course. The following blog post covers mergesort and quicksort.

Sorting means arraying an array of N items into ascending order by a natural order.

A natural order is generally defined as an order that is natural to humans. For instance, 1, 2, 3, 10, 20, 30 naturally ordered as opposed to a classic alphanumeric ordering, 1, 10, 11, 12, 2, 20, 21, 3.

The items must be of the same type, and is enforced by Java’s type system.

The implementation details of how a data type should be sorted is seperate from the sorting mechanism. In Java, this is achieved by requiring objects to be sorted to implement the Comparable interface:

public interface Comparable<Item> {
    public int compareTo(Item item);
}

The data type itself has to determine how the compareTo() method will work. Every data type that implements Comparable is required to have a compareTo() method. Below is the Java’s String compareTo method:

public int compareTo(String anotherString) {
    int len1 = value.length;
    int len2 = anotherString.value.length;
    int lim = Math.min(len1, len2);
    char v1[] = value;
    char v2[] = anotherString.value;

    int k = 0;
    while (k < lim) {
        char c1 = v1[k];
        char c2 = v2[k];
        if (c1 != c2) {
            return c1 - c2;
        }
        k++;
    }
    return len1 - len2;
}

The following logic is expected by a client using the method (i.e. a sort implementation). Let’s assume v is the item to be compared to another item, w:

  • return a negative integer when v is less than w
  • return 0 when v and w are equal
  • return a positive integer when v is greater than w

You can see String’s compareTo works in this fashion, as it uses the natural order of alphanumeric characters or the length of string.

Sorting Considerations

Certain considerations need to be taken when sorting. The following is not an exhaustive list.

  • certification: are the elements really sorted? how do we check?
  • time complexity: how is performance affected by array reads and writes?
  • space complexity: does the sort work in-place or does it hold another array copy during a sort?
    • in-place takes O(1) extra memory
  • stability: if a keys are equal, does the sort preserve the relative order of the items?
  • is it recursive or non-recursive? how will that affect memory usage?

Common operations in a sort

The are two common operations in sorting that are used across all sort methods. These are abstracted away into helper methods because they are so commonly used. They are the less() and exch() methods.

less() compares two Comparable items and returns a boolean value depending on whether the first item is less than or greater than the second item:

private static boolean less(Comparable v, Comparable w) {
    return v.compareTo(w) < 0;
}

exch() swaps two items in the array, which is a common operation in sorting. The current value of arr[i] is temporarily cached because arr[i] gets overwritten by value arr[j], and arr[j] is then set to the cached value:

private static void exch(Object[] arr, int i, int j) {
    Object swap = arr[i];
    arr[i] = arr[j];
    arr[j] = swap;
}

Mergesort

Profile of Mergesort:

  • is stable; keys maintain relative order
  • can be implemented in recursive (top-down) and iterative (bottom-up) variations
  • worst case running time is O(N * logN)
  • it’s prime disadvantage is it uses extra space proportional to array size N, so it’s grows by an order of O(N)

“top-down” mergesort works as a divide and conquer algorithm. Divide and Conquer problems are recursively broken down into subproblems until some base case is reached. In Mergesort’s case, arrays are broken down into subarrays. The smallest “problem” is a single entry array, because a one item array is sorted by default.

public class Merge {
    private static Comparable[] aux;  // auxillary array for merges

    public static void sort(Comparable[] arr) {
        aux = new Comparable[arr.length];  // allocate space just once
        sort(arr, 0, arr.length-1);
    }

    // sort arr[lo..hi]
    private static void sort(Comparable[] arr, int lo, int hi) {
        if (hi <= lo) return;

        int mid = lo + (hi - lo)/2;

        // sort left-half subarray
        sort(arr, lo, mid);
        // sort right-half subarray
        sort(arr, mid+1, hi);

        merge(arr, lo, mid, hi);
    }

    private static void merge(Comparable[] arr, int lo, int mid, int hi) {
        int i = lo;     // pointer for left-half
        int j = mid+1;  // pointer for right-half

        // copy to static auxillary array
        for (int k = lo; k <= hi; k++) aux[k] = arr[k];

        // merge back to arr[lo..hi]
        for (int k = lo; k <= hi; k++) {

            // copy remainder of right-half subarray to `arr` if left-half
            // subarray is  exhausted
            if (i > mid) arr[k] = aux[j++];

            // copy remainder of left-half subarray to `arr` if right-half
            // subarray is exhausted
            else if (j > hi) arr[k] = aux[i++];

            // most often these two lines are run in the loop - 
            // comparing aux[j] to aux[i]
            else if (less(aux[j], aux[i])) arr[k] = aux[j++];
            else arr[k] = aux[i++];
        }
    }    
}

Quicksort

Profile of Quicksort:

  • unstable; items in the array do not necessarily stay in their natural order
  • the average case running time is O(N * logN)
  • the worst case running time is O(N^2), but it is almost impossible for time complexity to be this bad (see below)
  • average case space complexity is O(logN) and works in-place (versus Mergesort’s requirement for an auxillary array)
  • don’t use for small arrays

Quicksort is another D&C algorithm. It works as an in-place sorting method using partitioning to break arrays into subarrays. The point of partition for each array is called the pivot.

Array contents must be shuffled before any sorting or partitioning takes place in order to avoid the worst case running time. If the array is sorted or reverse-sorted, it will take quadratic time.

The basic steps are:

  1. shuffle the array (ie using Knuth Shuffle)
  2. select a pivot and partition the array so:
    • entries smaller than the pivot are to the left of it
    • entries larger than the pivot are to the right of it
  3. recursively call step 2 on the subarrays until the base case of 1 array entry is reached
public class Quick {
    public static void sort(Comparable[] arr) {
        StdRandom.shuffle(arr);
        sort(arr, 0, arr.length - 1);
    }

    private static void sort(Comparable[] arr, int lo, int hi) {
        if (hi <= lo) return;

        int  = partition(arr, lo, hi);
        // recursive call sort left-of-pivot: arr[lo..j-1]
        sort(arr, lo, j-1);
        // recursive sort right-of-pivot: arr[j+1..hi]
        sort(arr, j+1, hi);
    }

    private static int partition(Comparable[] arr, int lo, int hi) {
        int i = lo;
        int j = hi + 1;
        Comparable v = arr[lo];

        // scan right, scan left, check for scan complete, and exchange
        while (true) {
            // these inner while-loops are incrementing the pointers for the 
            // left of pivot (`i`) and right of pivot (`j`) subarrays

            // find item in left-of-pivot subarray to swap
            while (less(arr[++i], v)) 
                if (i == hi) break;

            // find item in right-of-pivot subarray to swap
            while (less(v, arr[--j])) 
                if (j == lo) break;

            // if the pointers cross, exit the while-loop
            if (i >= j) break;

            // otherwise, swap the current `i`th and `j`th items
            exch(arr, i, j);
        }

        exch(arr, lo, hi);  // put partitioning item v into arr[j];
        return j;  
    }        
}

Final Notes

Java uses Mergesort to sort objects and Quicksort to sort primitive types. Based on this Stackoverflow question, the reasons are:

  1. Being that Quicksort is not stable, it might cause unwanted swaps for an Object array. For primitive types, this is not an issue as they have no identity
  2. Memory usage - because Mergesort doubles the memory necessary with an O(n) space complexity, it’s generally expected the reference types used in an array of objects will take up more memory, so adding slightly more overhead for the benefit of a stable sort is trivial.