We want to develop an algorithm that sorts an array of elements efficiently. Our strategy will be simple; we will somehow try to divide the array into two halves in such a way that sorting each half will complete the sorting. If we can achieve this, we can recursively call the sorting algorithm this way. We already know that the number of levels of recursive call will be of the order of lg n where lg m is the logarithm of m with the base 2. So, if we can manage to cut the array in a time in the order of n, we will still have a complexity of O(n lg n) This is much better than O(n ²), which we saw in the previous chapter. But how do we cut the array that way? Let's try to cut the following array as follows:

10, 5, 2, 3, 78, 53, 3,1,1,24,1,35,35,2,67,4,33,30

If we trivially cut this array, each part will contain all sorts of values. Sorting these individual parts would then not cause the entire array to be sorted. Instead, we have to cut the array in such a way that all the elements in the left part are less than all the elements in the right part. If we can achieve this, sorting the parts will achieve sorting the whole. But, of course, we need to make some swaps for us to be able to cut the array in such a way. So, we use the following trick:

This is an example of pivot positioning in quicksort. The one headed arrows represent comparison and double headed arrows represent swap.

We first choose the last element and call it pivot. Our aim is to make all the elements that are less than the pivot to be on its left and all the elements that are greater than the pivot to be on its right. Note that this means that the pivot is already at the correct position of the array. The preceding figure shows how to do it with an example. In the figure, our pivot is 30. We start comparing with the first element and move on. The moment we find an inversion, we swap the pivot with that element and keep comparing in the opposite direction. We continue this way, swapping every time there is an inversion and reversing the direction of comparison each time. We stop when all the elements have been compared. Note that after this process, all the elements less than the pivot are on its left, and all the elements greater than the pivot are on its right. Why does this work? Let's take a closer look.

Suppose we start comparing from the left. After the first swap, the pivot is at the position of the element that was found to be greater than it. All the elements that were on the left of it have already been compared with the pivot and found to be less than it. The previous figure shows the parts that have already been compared. Now it starts comparing from its earlier position in the opposite direction. After the second swap, it sits in the position of the element that it has been swapped with. All the elements on the right have already been compared with it and found to be greater than it. We keep going in the same way, always ensuring that the parts that have already been compared follow the rule that the part on the left of the pivot contains only elements that are less than or equal to it and the part on the right of the pivot contains only elements that are greater than or equal to it. So, when we are done with the comparisons, we still hold this condition, thus achieving the result. Once we know that all the elements on the left of the pivot are less than or equal to all the elements that are on its right, we can sort these parts separately and the entire array will be sorted as a result. Of course, we sort these parts recursively in the same way.

However, before we dive into the code, I would like to introduce a different interface for comparison. It is called java.util.Comparator and allows us to specify any comparison logic while sorting, thus providing more flexibility. Here is how it looks:

@FunctionalInterface 
public interface Comparator<T> { 
     int compare(T o1, T o2); 
}

This is, of course, a very simplified version of the actual interface but has got all that we care about. As you can see, this is a functional interface and thus can be implemented using a lambda. It should return the same value that is conceptually similar to the value returned by o1.compareTo(o2), but a different sorting can use a different comparison lambda. The compare method has to follow the same rules that are there for the compareTo method in the java.util.Comparable interface we studied in the previous chapter.

Now let's jump into the code for quicksort. We know we don't have to sort any more when the array to be processed is empty, which would be our base case. Otherwise, We create two indexes i and j, one storing the current end of the left part and the other storing the current beginning of the right part that has already been compared with the pivot at any given point of time, while the pivot is being placed in its correct position. Both the index variables store the indexes that are to be compared next. At any given point of time, one of these variables holds the position of the pivot and the other stores the current value being compared with it. The variable that currently stores the position of the pivot is flagged by the Boolean variable, movingI. If it is true, it means that we are currently moving i and hence, j is pointing to the pivot. We update the position variables and keep comparing, in a loop, until both indexes point to the pivot, when the comparison suggests that there is an inversion, we swap and reverse the direction of movement. We reverse the direction of movement because the pivot has moved to the position indexed by the opposite variable, marked by movingI switching its value. Otherwise, we just keep updating the appropriate position variable.

When movingI is false, it means that i is storing the position of the pivot. And finally, when the pivot is at the correct position and all the elements on its left are less than or equal to all the elements on its right, we recursively call quicksort on each part:

public static <E> void quicksort(E[] array, int start, int end,
Comparator<E> comparator) {

    if (end - start <= 0) {
        return;
    }

    int i = start;
    int j = end - 1;
    boolean movingI = true;

    while (i < j) {

    if (comparator.compare(array[i], array[j]) > 0) {
        swap(array, i, j);
        movingI = !movingI;
    } else {
        if (movingI) {
            i++;
        } else {
            j--;
            }
        }
    }

    quicksort(array, start, i, comparator);
    quicksort(array, i + 1, end, comparator);
}

We can wrap this method to avoid having to pass the start and end parameters:

public static <E> void quicksort(E[] array, Comparator<E> comparator){
    quicksort(array, 0, array.length, comparator);
}

We can use this method to sort an array. Let's see how to sort an integer array:

Integer[] array =
new Integer[]{10, 5, 2, 3, 78, 53, 3, 1, 1, 24, 1, 35,
35, 2, 67, 4, 33, 30};

quicksort(array, (a, b) -> a - b);
System.out.println(Arrays.toString(array));

The following would be the output:

[1, 1, 1, 2, 2, 3, 3, 4, 5, 10, 24, 30, 33, 35, 35, 53, 67, 78]

Note how we passed the simple comparator using a lambda. If we pass a lambda (a,b)->b-a instead, we will get the array reversed. In fact, this flexibility lets us sort arrays containing complex objects according to any comparison we like. For example, it is easy to sort an array of Person objects by age using the lambda, (p1, p2)->p1.getAge() - p2.getAge().

T(n) = T(n-1) + a(n-1) + b where a and b are some constants.
=> T(n) – T(n-1) = a(n-1) + b

T(n) – T(n-1) = a(n-1) + b
T(n-1) – T(n-2) = a(n-2) + b
T(n-2) – T(n-3) = a(n-3) + b
...
T(2) – T(1) = a(1) + b

T(n) – T(1) = a (1+2+3+...+(n-1)) + (n-1)b
=> T(n) – T(1) = an(n-1)/2 + (n-1)b
=> T(n) = an(n-1)/2 + (n-1)b + T(1)
=> T(n) = O(n2)

T(n) = 2T((n-1)/2) + a(n-1) + b

T(n) = 2T(n/2) + a(n-1) + b

S(m) = 2S(m-1) + a 2m + (b-a)

S(m) = 2(2S(m-2) + a 2m-1 + (b-a)) + a 2m + (b-a)
=> S(m) = 4 S(m-2) + a (2m + 2m) + (b-a)(2+1)

S(m) = 8 S(m-3) + a (2m + 2m  + 2m) + (b-a)(4+2+1)
…
S(m) = 2m S(0) + a (2m+ 2m  + 2m+ 2m) + (b-a)(2m-1+ 2m-2+ … + 2+1)
=>S(m) = 2m S(0) + a m . 2m+ (b-a) (2m – 1)
=> T(n) = nT(1) + a . (lg n) . n + (b-a) (n-1)
=> T(n) =  θ(n lg n)

public static <E> void quicksort(E[] array, int start, int end,
Comparator<E> comparator) {
    if (end - start <= 0) {
        return;
    }
    int pivotIndex = (int)((end-start)*Math.random()) + start;
    swap(array, pivotIndex, end-1);
    //let's find the pivot.
    int i = start;
    int j = end - 1;
    boolean movingI = true;
    while (i < j) {
        if (comparator.compare(array[i], array[j]) > 0) {
            swap(array, i, j);
            movingI = !movingI;
        } else {
            if (movingI) {
                i++;
            } else {
                j--;
            }
        }
    }
    quicksort(array, start, i, comparator);
    quicksort(array, i + 1, end, comparator);
}