How to Use the sort Method for Quicksort in Java - dummies

How to Use the sort Method for Quicksort in Java

By Doug Lowe

One of the most commonly used sorting techniques in Java is called the Quicksort technique. It’s a great way to deal with recursion. The actual code that drives a Quicksort routine is surprisingly simple:

public static void sort(int low, int high)
{
 if (low >= high)
  return;
 int p = partition(low, high);
 sort (low, p);
 sort (p+1, high);
}

This method sorts the portion of an array indicated by the low and high index values passed to it. Ignoring the if statement for now, the sort method works by calling a partition method. This method rearranges the array into two partitions so that all the values in the left partition are smaller than all the values in the right partition.

The partition method returns the index of the end of the left partition. Then the sort method calls itself twice: once to sort the left partition and again to sort the right partition.

To get the sort method started, you call it with 0 as the low value and the array length and 1 as the high value. Thus the sort method begins by sorting the entire array. Each time the sort method executes, it calls itself twice to sort smaller partitions of the array.

The if statement at the beginning of the sort method compares the low value with the high value. If the low value is equal to or greater than the high value, the partition has only one element (or perhaps no elements) and therefore is already sorted. In that case, the sort method simply returns without calling itself again. That’s the condition that ends the recursion.