Stack Overflow Error Implementing Quicksort (with duplicates) in C#

Question

I am working on a project and I have to implement Quicksort. I am having a stack overflow issue when I run Quicksort on an array of random integers (of size 100,000). I believe that I am running into an error that involves duplicate values. I attempted to research this problem and someone mentioned to consider when data[left] == pivot == data[right] but I don't know what to do with that in my case.

This is for my class so I am required to use this partitioning method, and I created the Quicksort method based off of instructions. Any help will be greatly appreciated. I'd like to figure out what I am doing wrong.

public static int Partition(int[] a, int left, int right, int pivotIndex) {
   int temp;
   int pivotValue = a[pivotIndex];
   a[pivotIndex] = a[right];
   a[right] = pivotValue;

   int store = left;
   for (int i = left; i < right; i++) {
      if (a[i] < pivotValue) {
         temp = a[store];
         a[store] = a[i];
         a[i] = temp;
         store++;
      }
   }
   temp = a[right];
   a[right] = a[store];
   a[store] = temp;

   return store;
}

public static void Quicksort(int[] a, int left, int right) {
   if ((right - left) <= 5)
      InsertionSort(a);
   else if (left < right) {
      int mid = ((right - left) / 2) + left;
      int pivot = Math.Max(Math.Min(a[left], a[right]), Math.Min(Math.Max(a[left], a[right]), a[mid]));
      int pivotIndex = Array.IndexOf(a, pivot);

      Partition(a, left, right, pivotIndex);
      Quicksort(a, left, (pivotIndex - 1));
      Quicksort(a, (pivotIndex + 1), right);
   }
}

Answer 1

Your problem is in the way you choose the pivot index.

Although you are correctly choosing the median of three value, you are not finding the index of that median correctly.

Firstly, this is incorrect:

int pivotIndex = Array.IndexOf(a, pivot);

That will find the index of the first occurrence of the median value in the entire a[] array.

At the very least it should be like this:

int pivotIndex = Array.IndexOf(a, pivot, left, right-left+1);

However that still has several problems:

1. You will be doing a linear search for the pivot value over the entire partition. This is very inefficient.
2. It will find the first occurrence of the median value, regardless of what the actual index is.
3. If the left, right or mid values are the same, it should choose the mid index, but the linear search will choose the left index.

The solution is to change the way you compute the median of three so that you calculate the actual index rather just the value. This is rather more fiddly!