Recursive QuickSort suffering a StackOverflowException -- Need fresh eyes
- by jon
I am working on a Recursive QuickSort method implementation in a GenericList Class. I will have a second method that accepts a compareDelegate to compare different types, but for development purposes I'm sorting a GenericList<int
I am recieving stackoverflow areas in different places depending on the list size.
I've been staring at and tracing through this code for hours and probably just need a fresh pair of (more experienced)eyes. Definitely wanting to learn why it is broken, not just how to fix it.
public void QuickSort()
{
int i, j, lowPos, highPos, pivot;
GenericList<T> leftList = new GenericList<T>();
GenericList<T> rightList = new GenericList<T>();
GenericList<T> tempList = new GenericList<T>();
lowPos = 1; highPos = this.Count;
if (lowPos < highPos)
{
pivot = (lowPos + highPos) / 2;
for (i = 1; i <= highPos; i++)
{
if (this[i].CompareTo(this[pivot]) <= 0)
leftList.Add(this[i]);
else
rightList.Add(this[i]);
}
leftList.QuickSort();
rightList.QuickSort();
for(i=1;i<=leftList.Count;i++)
tempList.Add(leftList[i]);
for(i=1;i<=rightList.Count;i++)
tempList.Add(rightList[i]);
this.items = tempList.items;
this.count = tempList.count;
}
}
