QuickSort

Algorithm: If the array contains only one element or zero elements then the array is sorted.

If the array contains more then one element then:

• Select an element from the array. This element is called the "pivot element". For example select the element in the middle of the array. (choose the middle one)
• All elements which are smaller then the pivot element are placed in one array and all elements which are larger are placed in another array.
• Sort both arrays by recursively applying Quicksort to them.
• Combine the arrays

Quicksort can be implemented to sort "in-place". This means that the sorting takes place in the array and that no additional array need to be created.

QuickSort can be accomplished the best in O(nlogn), the worst in O(n2).

Reference: here

 public class QuickSort {  
   public void quickSort(int[] A) {  
     if (A == null || A.length < 2)  
       return;  
     helper(A, 0, A.length-1);  
   }  
   public void helper(int[] A, int low, int high) {  
     if (A == null || A.length < 2)  
       return;  
     int pivot = (low + high) / 2;  
     int i=low, j = high;    
     while (i <= j) {  
       while (A[i] < A[pivot])  
         i++;  
       while (A[j > A[pivot]])  
         j--;    
       if (i < j) {  
         change(A, i++, j--);  
       }  
     }  
     if (low < j) helper(A, low, j); 
     if (i < high) helper(A, i, high);
   }  
   public void change(int[] A, int i, int j) {  
     int temp = A[i];  
     A[i] = A[j];  
     A[j] = temp;  
   }  
 }