# Quicksort with insertion Sort finish - where am I going wrong?

I am working on a project for a class. We are to write a quick-sort that transitions to a insertion sort at the specified value. Thats no problem, where I am now having difficulty is figuring out why I am not getting the performance I expect.

One of the requirements is that it must sort an array of 5,00,000 ints in under 1,300 ms (this is on standard machines, so CPU speed is not an issue). First of all, I can't get it to work on 5,000,000 because of a stack overflow error (too many recursive calls...). If I increase the heap size, I am still getting a lot slower than that.

Below is the code. Any hints anyone?

public class MyQuickSort {

public static void sort(int [] toSort, int moveToInsertion)
{
sort(toSort, 0, toSort.length - 1, moveToInsertion);
}

private static void sort(int[] toSort, int first, int last, int moveToInsertion)
{
if (first < last)
{
if ((last - first) < moveToInsertion)
{
insertionSort(toSort, first, last);
}
else
{
int split = quickHelper(toSort, first, last);
sort(toSort, first, split - 1, moveToInsertion);
sort(toSort, split + 1, last, moveToInsertion);
}
}
}

private static int quickHelper(int[] toSort, int first, int last)
{
sortPivot(toSort, first, last);
swap(toSort, first, first + (last - first)/2);
int left = first;
int right = last;
int pivotVal = toSort[first];
do
{
while ( (left < last) && (toSort[left] <= pivotVal))
{
left++;
}

while (toSort[right] > pivotVal)
{
right--;
}

if (left < right)
{
swap(toSort, left, right);
}

} while (left < right);

swap(toSort, first, right);

return right;
}

private static void sortPivot(int[] toSort, int first, int last)
{
int middle = first + (last - first)/2;

if (toSort[middle] < toSort[first]) swap(toSort, first, middle);

if (toSort[last] < toSort[middle]) swap(toSort, middle, last);

if (toSort[middle] < toSort[first]) swap(toSort, first, middle);

}

private static void insertionSort(int [] toSort, int first, int last)
{
for (int nextVal = first + 1; nextVal <= last; nextVal++)
{
int toInsert = toSort[nextVal];
int j = nextVal - 1;
while (j >= 0 && toInsert < toSort[j])
{
toSort[j + 1] = toSort[j];
j--;
}
toSort[j + 1] = toInsert;
}
}

private static void swap(int[] toSort, int i, int j)
{
int temp = toSort[i];
toSort[i] = toSort[j];
toSort[j] = temp;
}

}

I haven't tested this with your algorithm, and I don't know what kind of data set you're running with, but consider choosing a better pivot than the leftmost element. From Wikipedia on Quicksort:

Choice of pivot In very early versions of quicksort, the leftmost element of the partition would often be chosen as the pivot element. Unfortunately, this causes worst-case behavior on already sorted arrays, which is a rather common use-case. The problem was easily solved by choosing either a random index for the pivot, choosing the middle index of the partition or (especially for longer partitions) choosing the median of the first, middle and last element of the partition for the pivot

Figured it out.

Actually, not my sorts fault at all. I was generating numbers between the range of 0-100 (for testing to make sure it was sorted). This resulted in tons of duplicates, which meant way to many partitions. Changing the range to min_int and max_int made it go a lot quicker.

Thanks for your help though :D