Quick Sort in Java

Quick sort is one of the coolest algorithms available in sorting and its performance is measured most of the time in O(nlogn), although the worst case sorting times of bubble sort and this are equal.
Inspite its worst case time, this always performs superiorly when the input is completely shuffled/randomized. This is one of the modest sorts available :).

Quick sort is an example of in-place sort. No extra space is needed as in merge sort where we have to use one full extra array to hold all the merged values. The only space that quick sort uses may be the counter variables and the extra space required for swapping.

Below is a pictorial representation of how this quick sort works,

I ran this sort for a well randomized data of million elements again and again and it beats the Merge sort hands down having a 75% quicker speed. Its always advisable to have shuffle the data upfront before running this algorithm.
Here is the source code for the same,

package dsa.sorting;

/**
 * A wonderful inplace sorting technique
 * @author Braga
 */
public class QuickSort {
 
 public static int SIZE = 1000000;

 public int[] sort(int[] input) {
  quickSort(input, 0, input.length-1);
  return input;
 }
 
 public static void main(String args[]){
  int[] a = new int[SIZE];
  for(int i=0;i<SIZE;i++){
   a[i] = (int)(Math.random()*SIZE);
  }
  QuickSort mNew = new QuickSort();
  long start = System.currentTimeMillis();
  mNew.sort(a);
  long end = System.currentTimeMillis();
  System.out.println("Time taken to sort a million elements : "+(end-start)+" milliseconds");
 }
 
 public void print(int[] inputData) {
  for(int i:inputData){
   System.out.print(i+" ");
  }
  System.out.println();
 }
 
 private void quickSort(int arr[], int left, int right) {
  int index = partition(arr, left, right);
  if (left < index - 1)
   quickSort(arr, left, index - 1);
  if (index < right)
   quickSort(arr, index, right);
 }
 
 private int partition(int arr[], int left, int right) {
  int i = left, j = right;
  int tmp;
  int pivot = arr[(left + right) / 2];
  while (i <= j) {
   while (arr[i] < pivot)
    i++;
   while (arr[j] > pivot)
    j--;
   if (i <= j) {
    tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
    i++;
    j--;
   }
  }
  return i;
 }
}
//Time taken to sort a million elements : 156 milliseconds

Pros:
1) Efficient average case compared to any algorithm.
2) Recursive definition and popularity because of its high efficiency.

Cons:
1) Worst case scenario sucks.

As we discussed the worst case can be easily overcome by deliberately shuffling the input. I would rate quick sort as one of the best techniques available in sorting till date.

More sorting methods yet to come.
Cheers,
Bragaadeesh.