Quicksort - slower on sorted arrays?

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?