Quicksort - slower on sorted arrays?

Question

so i am trying out some sorting algorithms.

private static void quicksort(int[] list, int low, int high){
    int pivot = list[low + (high-low)/2];
    int i = low; 
    int j = high;
    while (i <= j) {
      while (list[i] < pivot) {
        i++;
      }
      while (list[j] > pivot) {
        j--;
      }
      if (i <= j) {
        int temp = list[i];
        list[i] = list[j];
        list[j] = temp;
        i++;
        j--;
      }
    }
    if (low < j){
        quicksort(list, low, j);
    }
    if (i < high){
        quicksort(list, i, high);
    }

}

This code runs on two arrays of integers with x entrys each (lets say 1 billion). The first one is sorted and the second one is a permutation on array 1, where n pairs are randomly chosen and switched.

I choose the middle element as pivot so it should be optimal for the sorted case, right?

I am measuring the time the algorithm takes to sort each array and count how many switches and steps of recursion occur. As expected both of these values are higher for sorting array 2 with the random permutations.

But: the algorithm still takes longer to process the sorted array until i reach a high number of permutations. For n=10000 i get something like 20ms for the unsorted array and 30ms for the sorted one. Why is that?

Answer 1

Best I can say so far is that you should double-check your timing. In general profiling like this should be done as an average over many runs. I made a test class based on your code and got these results:

This was done using System.nanoTime() as my profiling tool. Nothing fancy.

edit: Here's a link to the profiling class I wrote. It outputs results in CSV-like format so I could make the graph in a spreadsheet program.

Answer 2

The worst case scenario for quickSort algorithm is when the array is sorted or almost sorted. That is most likely why it takes you longer time sorting the array which is already sorted.