In my previous article about sorting algorithms we looked at the basic sorting algorithms in computer science: Selection Sort, Bubble Sort, and Insertion Sort. These are relatively basic algorithms because they're intuitive, but also because they're not all that efficient. In this post we'll look at the two sorting algorithms that are the most often used in software to implement sorting. And why are these the most often used? Because they're fast, with an average runtime of O(n*log(n)).

Let's start with my favorite of the two, merge sort.

Merge Sort

Think of a list of 1,000,000 items. Then think of a list of 2 items. Which is easier to sort? Well what if we broke that 1,000,000 item list down into 500,000 lists of 2 items. Would breaking the list up into sublists help us sort the list faster?

Merge sort uses this type of divide and conquer strategy. It takes the list and divides it into smaller and smaller lists. It sorts these smaller lists and then merges the sorted sublists together.

Below is a visual of how this works:

Notice how you have two distinct steps in this algorithm:

1. Split lists in half over and over until you're down to list of size 1.
2. Merge these lists back together, sorting the elements as you merge.

Take a look at the whole thing in a single picture and see how this process can be represented as a graph or tree:

Hopefully these visuals give you an idea of how this algorithm can be implmented in Java.

Implementation

Let's check out the implementation below:

public class Sort {

    public static void main(String[] args) {
        int[] unsorted = { 6, 5, 1, 4, 3 };
        mergeSort(unsorted);
        printArrayOf(unsorted);
    }

    private static int[] mergeSort(int[] arr) {                     
        if (arr.length <= 1) {
            return arr;
        }
        int[] left = mergeSort(split(0, arr.length / 2, arr));
        int[] right = mergeSort(split(arr.length / 2, arr.length, arr));

        return merge(left, right, arr);
    }

    private static int[] split(int start, int end, int[] arr) {
        int[] result = new int[end - start];
        for (int i = start; i < end; i++) { 
            result[i - start] = arr[i];             
        }
        return result;
    }

    private static int[] merge(int[] left, int[] right, int[] arr) {
        int i = 0;
        int j = 0;
        while (i < left.length && j < right.length) {
            if (left[i] < right[j]) {          
                arr[i + j] = left[i]; 
                i++;
            } else {    
                arr[i + j] = right[j]; 
                j++;
            }
        }
        while(i < left.length) {
            arr[i + j] = left[i]; 
            i++;
        }
        while (j < right.length) {
            arr[i + j] = right[j]; 
            j++;
        }
        return arr;
    }

    private static void printArrayOf(int[] arr) {
        for (int value : arr) {
            System.out.print(" " + value + " ");
        }
    }
}

The split portion of this algorithm is pretty easy to grasp. We split the array in half and pass the left half into the mergeSort() function and the right half into the mergeSort() algorithm. Our split() method takes a start index, an end index, and an array to split. The implementation is prtty simple. Another option instead of implementing split() yourself is to use the built in Arrays.copyOfRange() method which does the exact same thing.

So once we split our array the algorithm recurses, using the same method over and over until we reach our base case. The base case of course, is when the passed in array has one or less elements. That's when we reach the bottom of the tree. Once we've reached the base case we come back up the recursive stack and our method has a right array and a left array. This is where we merge the two arrays together into sorted order.

We pass the left, right, and original array off to a helper method called merge(). Inside merge() we declare two pointers, one for our left array and one for our right array. The while loop checks the elements in the left and right arrays at their pointers and compares them. Whichever element is lower is added to the i + j index of our orginal array. This process continues until we check all elements in left or in right. At this point, if an array still has elements to check (it's counter is less than its length) then all of these values can be filled into the end of the original array arr.

In the end, the implementation does exactly what you'd expect from the visual above, splitting until we've reached arrays of size one, and then merging these arrays back together in sorted order.

Merge Sort is an O(nlog(n)) complexity algorithm in all cases. How do we arive at that number? Anytime we are splitting in half and recursing, the algorithm has O(log(n)) runtime. So the splitting of the array until halves ends up taking O(log(n)) time. Then the merge function has a set of while loops in it. Each time this method is called it loops n times, where n is the size of the array arr that is passed in. Thus, for every step back up the recursive stack, merge() runs n times.
So O(log(n) as the algorithm recusrse down the stack, and O(n) as it recurses up the stack. Thus the overall complexity of mergeSort() is O(nlog(n)).

Also note, in my implmentation above I return a copy of the orignal array. Thus the algorithm is not very memory efficient, but you can implement mergeSort to update the array in memory instead of making a copy. This would be the ideal implementation for memory efficiency.

For more help visualizing how Merge Sort is O(n*log(n)) check out the image below:

This is about as good as it gets as far as sorting alogirthms go, but there is another commonly used algorithm with equal efficiency.

Quick Sort

Quick Sort is probably the most difficult sorting algorithm to implement. Like Merge Sort, it takes advantage of recursion, but instead of dividing and conquering, quick sort uses a pivot values to aid in sorting all the elements in the array. Let's see how it works.

1. With an array of n element, pick a pivot value at random.
2. Partition the array around this pivot, such that all elements less than the pivot are to the left of the pivot and all elements greater than the pivot are to the right. These partitions can be unsorted.
3. Repeat recursively with each subarray: that of elements less than the pivot (elements to the left) and that of elements greater than the pivot (elements to the right).

Take a look at the visual and try to see where each step comes in.

With the steps in mind let's take a look at the implementation.

public class Sort {

    public static void main(String[] args) {
        int[] unsorted = { 6, 5, 1, 4, 3 };
        quickSort(unsorted);
        printArrayOf(unsorted);
    }

    public static int[] quickSort(int[] arr) {
        return quickSort(arr, 0, arr.length - 1);
    }

    private static int[] quickSort(int[] arr, int left, int right) {
        if (left < right) {
            int pivotIndex = partition(left, right, arr);

            quickSort(arr, left, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, right);

        }

        return arr;
    }

    private static int partition(int left, int right, int[] arr) {
        Random rand = new Random();
        int pivotIndex = left + (rand.nextInt(right - left + 1));
        int pivot = arr[pivotIndex];
        swap(pivotIndex, right, arr);
        int j = left; 
        for (int i = left; i < right; i++) {
            if (arr[i] <= pivot) { 
                swap(i, j, arr);
                j++;
            }
        }
        swap(j, right, arr);
        return j;
    }

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

    private static void printArrayOf(int[] arr) {
        for (int value : arr) {
            System.out.print(" " + value + " ");
        }
    }

}

In contrast to my Merge Sort implementation this implementation sorts the array in place instead of returning an array copy.

There are two sections: partition and recurse. In the partition section, we choose a pivot at random. We swap the pivot and the right most value in the passed in array so that the pivot is all the way to the right of our array. This makes it easy for our algorithm to walk through the other elements in the array from left to right and move them around based on their relationship to the pivot.

The for loop in the partition method does just that. With a counter j which is initalized to left (or the first element in the passed in array) we separate the values in the array based on whether their less than or greater than our pivot. We keep track of this division with our counter j. So if a value is less than our equal to our pivot, we swap it with the value at j and increment j. Once done with this process, we insert our pivot (which is currently at right) into the correct spot in the array, between the values less than and greater than it.

Our concatenate section is very thin, as it simply calls quickSort() on the section of the array to the left of the pivot and on the section to the right of the pivot. This essentially sorts the left sub array and the righ sub array using the same algorithm.

Once complete, the array is sorted.

Resources

There are tons of other resources out there to learn about these sorting algorithms. I gained my knowledge through my degree, but also used Educative to brush up on my algorithm skills. Check out their course on algorithms here.