The quick-sort algorithm (AKA partition exchange sort) is one of the fastest known in-memory sorting algorithms in practice, though its worst-case timing is actually worse than merge-sort. The algorithm is interesting from an academic point of view, but in real applications, sorting isn’t a massive problem until data sets become too large to sort on a single node. Quick sort typically isn’t used once this occurs.

How Does it Work?

Quick sort works by finding a pivot point (the middle element in this case for ease), moving all elements less than the pivot element to the left of it, and all elements greater than the pivot to the right of it, then recursing to do the same thing to the left half of the array and the right half of the array. This continues until only one element is left at the given level. By this point, the whole array is element sorted.

Execution Time and Characteristics

Quick sort is a n * lg(n), non-stable sorting algorithm in its average case, which makes it relatively fast. It actually outperforms mergesort in the average case, which is also n * lg(n). The problem with quick sort is that its worst-case running time is actually n^2, and while this performance is rare, it is unacceptable in many applications. Also, unstable sorts can cause problems in some applications which also leads to merge-sort being favored in many language libraries (e.g. Java Collections.sort()).

Sample Implementation

Here is a sample implementation of the Quick Sort algorithm which is heavily commented to aid in helping you to understand what it is doing. It is a full implementation, so feel free to double-click and copy the whole thing to an IDE so that you can watch it work through a debugger to aid your learning process.

 import java.util.Arrays;

 public class QuickSort {

     //Sample main method for testing the algorithm.
     public static void main(String[] args) {
         int a[] = { 9, 2, 8, 7, 1, 9, 6, 4, 2, 5, 9 };
         System.out.println("Before sorting:" + Arrays.toString(a));
         QuickSort sorter = new QuickSort();
         sorter.sort(a);
         System.out.println("After sorting:" + Arrays.toString(a));
     }

     //The array to be sorted.
     private int[] a;

     public QuickSort() {
         //Nothing to do.
     }

     //Verify array contents and call the underlying sort function.
     //TODO: Avoid storing array locally to make this thread-safe.
     public void sort(int[] a) {
         if (a == null || a.size() >> 1];
         int i = start;
         int j = end;

         //Process the given range of the array, moving i right and
         //j left until i is greater than j.
         while (i <= j) {

             //Advance i until it is not less than the pivot value.
             while (a[i]  pivot) --j;   

             //If i hasn't moved past j, swap the i value
             //(>= pivot on left) for the j value
             //(<= pivot on the right).  This allows us to
             //swap the high values on the left for the low values
             //on the right which sorts the array.
             if (i <= j) swap(i++, j--);
         }

         //Recurse to the left and right lists if there is work to
         //do in either. We moved i from the left and j from the
         //right until j was before i. So, the sub-lists that we 
         //will recurse to are start through j, and i through end.
         if (start  i) quickSort(i, end);
     }

     private void swap(int i, int j) {
         int tmp = a[i];
         a[i] = a[j];
         a[j] = tmp;
     }
 }