Here is the overall strategy of QuickSort:

1. QuickSort chooses an arbitrary value from somewhere in the list. A common location is the middle value of the list.

2. This value becomes a decision point for roughly sorting the lis-t into two sublists, which are called the “left” and the “right” sublists. All the values smaller than the dividing value are placed in the left sublist, while all the values greater than the dividing value are placed in the right sublist.

3. Each sublist is then recursively sorted with QuickSort.

4. The termination of QuickSort occurs when a list of one value is obtained, which by definition is sorted.

This is the code for quickSort:

void quickSort ( ArrayList<Comparable> list, int first, int last )
{
  int g = first, h = last;

  int midIndex = (first + last) / 2;
  Comparable dividingValue = list.get( midIndex );
  do
  {
     while ( list.get(g).compareTo( dividingValue ) < 0 )
        g++;
     while ( list.get(h).compareTo( dividingValue ) > 0 )
        h--;
     if ( g <= h )
     {
        // swap(list[g], list[h]);
        swap( list, g, h );
        g++;
        h--;
     }
  } while ( g < h );

  if ( h > first )
     quickSort ( list,first,h );
  if ( g < last )
     quickSort ( list, g, last );
}

17 22 34 28 19 84 11 92 1

1. The values received by the formal parameter list in the first call of quickSort are a reference to an array, and the first and last cells of the array, 0 and 8. Variable first is initialized with the value 0, and last is initialized with the value 8.

2. The midIndex value is calculated as (0+8) / 2, which equals 4.

3. The dividingValue is the value in location 4, list[4] = 19.

4. The value of 19 will be our decision point for sorting values into two lists. The list to the left will contain all the values less than or equal to 19. The list to the right will contain the values larger than 19. Or simply put, small values go to the left and large values go to the right.

5. The identifiers g and h will be indices to locations in the list. The while loops will move g and h until a value is found to be on the wrong side of the dividing value of 19. The g index is initialized with the value of first and the h index is initialized with the value of last.

6. The g index starts at position 0 and moves until it “sees” that 22 is on the wrong side. Index g stops at location 1.

7. The h index starts at position 8. Immediately it “sees” that the value 1 is on the wrong side.

8. Since g <= h (1 <= 8), the values in list[1] and list[8] are swapped. After the values are swapped, index g moves one position to the right and index h moves one position to the left.

9. The values of the pointers are now: g = 2, h = 7. We continue the do-while loop until g and h have passed each other, that is when g > h. At this point, the lists will be roughly sorted, with values smaller than 19 on the left, and values greater than 19 on the right.

10. If the left sublist has more than one value, (which is determined by the h > first expression), then a recursive call of quickSort is made. This call of quickSort will send the index positions that define that smaller sublist.

11. Likewise, if the right sublist has more than one value, quickSort is called again and the index positions that define that sublist are passed.