Big O notation for quicksort implementation I am trying to find out what would be the Big O notation of a quick sort implementation I wrote. If I can get some analysis on the code, that would be great.

public class JavaApplication1 {

public static void main(String args[]) {

    int[] input = { 23, 31, 1, 21, 36, 72};
    System.out.println("Before sorting : " + Arrays.toString(input));
    quickSort(input); // sort the integer array using quick sort algorithm
    System.out.println("After sorting : " + Arrays.toString(input));

    // input with duplicates
    int[] withDuplicates = { 11, 14, 16, 12, 11, 15};
    System.out.println("Before sorting : " + Arrays.toString(withDuplicates));
    quickSort(withDuplicates); // sort the integer array using quick sort algorithm
    System.out.println("After sorting : " + Arrays.toString(withDuplicates));
}

/**
 * public method exposed to client, sorts given array using QuickSort
 * Algorithm in Java
 * @param array
 */
public static void quickSort(int[] array) {
   if(array.length &lt;= 1) return;
   int leftwall = 0;
   int rightwall  = array.length - 1 ;
   int pivot = array[array.length/2]; 
   rechelperquickSort(array,leftwall,rightwall,pivot); 
}


public static void rechelperquickSort(int[] array ,int left , int right , int pivot ){

    int idx;   
    idx = left;

    if(left&gt;=right) return;

    while(idx&lt;=right){

        if(pivot &gt; array[idx])swapinarray(array,left++,idx);

        idx++;
    }
    if(left &gt;= right) return;
    pivot = array[left+1];
    rechelperquickSort(array,left+1,right,pivot);
    rechelperquickSort(array,0,left,array[left/2]);
}

public static void swapinarray(int[] array,int leftelementidx, int rightelementidx){
    int tmp = array[leftelementidx];
    array[leftelementidx] = array[rightelementidx];
    array[rightelementidx] = tmp;    
}

}
Doesn't work

Your sort doesn't work on this array:

int[] input = { 4, 5, 3, 2, 6, 1};


The output is:

Before sorting : [4, 5, 3, 2, 6, 1]
After sorting : [1, 2, 3, 5, 4, 6]


What's wrong?

One problem with your quicksort is that it doesn't always rearrange items to the left and right of the pivot.  If you pick the pivot that is the smallest element in the array, no swaps will be made.  Thus, you should either pick the leftmost item to be the pivot so that "no swaps" will just work, or swap the pivot item into the correct spot after your loop is finished.

Another problem with it is that you have a hardcoded 0 which is wrong:

rechelperquickSort(array,0,left,array[left/2]);


That 0 there should be the original value of left passed into the array.  Otherwise you are creating more work.