What is mergesort?

Mergesort is a clever recursive sorting algorithm that uses a divide and conquer approach. While all the previous sorting algorithms we have seen are O(n^2), mergesort is O(n*log(n)). This means it is much faster for sorting large arrays. Try comparing one million squared vs one million times log(one million)! For very large sets, insertion/selection/bubble sort will not complete within a human lifetime, while mergesort will complete it in hours or days.

Pseudocode

//function mergeSort(array x) {
//   if x is just one item (or none), return
//   split x into two arrays, left and right
//   mergeSort(the left half)
//   mergeSort(the right half)
//   combine the two halves back into x
//}

For an array such as {4,1,3,2}, the execution would look like this:

//mergeSort({4,1,3,2})
//	mergeSort({4,1})
//		mergeSort({4}) returns 4
//		mergeSort({1}) returns 1
//      merge {4} and {1} to {1,4}
//  mergeSort({3,2})
//		mergeSort({3}) returns 3
//		mergeSort({2}) returns 2
//      merge {3} and {2} to {3,2}
//  merge {1,4} and {2,3} to {1,2,3,4}

The key observation is that merging two sorted arrays is an O(n) operation. We need only take items from the front of one array or the other.

Mergesort on a one dimensional array of ints:

import java.util.*;
public class MyProgram {
    public static void main(String[] args) {
        int[] x = {4,1,2,3};
        mergeSort(x);
        System.out.println(Arrays.toString(x));
    }
    static void mergeSort(int[] x) {
        if(x.length <= 1) return; //base case
		
		//Split x into two arrays, left and right
        int[] left = new int[x.length/2];
        int[] right = new int[x.length-left.length];
        for(int i = 0; i < x.length; i++) {
            if(i < left.length) left[i] = x[i];
            else right[i-left.length] = x[i];
        }
		
		//Recursively sort left and right
        mergeSort(left);
        mergeSort(right);
        
		//Merge left and right back into x
        for(int i=0,j=0,k=0 ; i < x.length; i++) {
            if(k>=right.length||(j<left.length&&left[j]<right[k])) {
                x[i] = left[j];
                j++;
            }else {
                x[i] = right[k];
                k++;
            }
        }
    }
}

An advanced minification

Clever use of Arrays.copyRangeOf and the postfix increment operator allow you to shrink the mergesort function significantly. This is not recommended for the sake of readability, but may be useful for learning purposes:

import java.util.*;
public class MyProgram {
    public static void main(String[] args) {
        int[] x = {4,1,2,3};
        mergeSort(x);
        System.out.println(Arrays.toString(x));
    }
	static void mergeSort(int[] x) {
		if(x.length <= 1) return;
		int[] left=Arrays.copyOfRange(x,0,x.length/2),right=Arrays.copyOfRange(x,left.length,x.length);
		mergeSort(left);
		mergeSort(right);
		for(int i=0,j=0,k=0;i<x.length; i++) 
			x[i]=(k>=right.length||(j<left.length&&left[j]<right[k]))?left[j++]:right[k++];
	}
}

What is quicksort?

Quick Sort is another fast algorithm that has an average case performance of O(n*log(n)). Unlike merge sort, quicksort also uses very little additional memory. However, quicksort does have a worst case performance of O(n^2).

The quicksort algorithm works by choosing one element (usually the middle element) as a pivot. The algorithm then sets two indices to start on the left and right halves of the array, separated by the pivot. The two indices then scan towards the pivot, and when we find an element that is out of place on both sides, we swap them. Once the scan is complete, we are guaranteed that the pivot element is in the correct position in the array, since all smaller items are left of it and all larger items are right of it. Finally, we recursively perform quicksort on the left and right halves of the array, until quicksort is performed on an array section of only one element.

The resulting code looks like this:

import java.util.*;
public class MyProgram {
    public static void main(String[] args) {
        int[] x = {4,1,2,3};
        quickSort(x);
        System.out.println(Arrays.toString(x));
    }
    static void quickSort(int[] values) {
		quickSort(values, 0, values.length - 1);
	}

	static void quickSort(int[] numbers, int low, int high) {
		if (numbers ==null || numbers.length==0) return;

		//Set pivot as middle of array
		int i = low, j = high, pivot = numbers[low + (high-low)/2]; 

		// Divide array to two parts using i and j as indices
		while (i <= j) { //shift left and right (i,j):
			while (numbers[i] < pivot) i++;
			while (numbers[j] > pivot) j--;

			if (i < j) { //swap numbers[i] and numbers[j]
				int temp = numbers[i];
				numbers[i] = numbers[j];
				numbers[j] = temp;
				i++;
				j--;
			}
		}
		
		//recurs
		if (low < j)  quickSort(numbers, low, j);
		if (i < high) quickSort(numbers, i, high);
	}
}