The quicksort i am building works for only aprox 50000 element in a list.
If i go above that i will run out of memory and the program will crash.

This is only when i use the median of three or left as my pivot element.
When i use random i can use lists up to atleast 1 million elements.

Is there a way to take care of the memory loss without the need of rewriting everything?

the pivotType is of user input and is sent along. And the array goes from nrOfElements -> 1.
If there is a need for more of my code, please do tell.

    array = (int *)malloc(nrOfElements * sizeof(int));

        void quickSort(int array[], int left, int right, int pivotType) {

            int pivotElement, i, j;

            if(left < right) {
                if (pivotType == 1)
                    pivotElement = leftPivot(array, left, right);
                if (pivotType == 2)
                     pivotElement = medianOfThreePivot(array, left, right); 
                if (pivotType == 3) 
                    pivotElement = randomPivot(array, left, right);

                i = left+1;
                j = right;

                while(i <= j) {
                    while(i <= right && array[i] <= pivotElement) 
                    while(j >= left && array[j] > pivotElement) 
                    if (i < j) 
                        swapElement(&array[i], &array[j]);
                    swapElement(&array[left], &array[j]);
                    quickSort(array,left,j-1, pivotType);
                    quickSort(array,j+1,right, pivotType);


    //after all quicksorts are done with all subarrays the
    free(array); is called
6 Years
Discussion Span
Last Post by Kerrai

could you give an example of which digit is chosen for leftPivot and median of three if it's an extreme(where the digits would be placed in a skewed pattern) then there's your problem... the wrong choice of pivot
just my assumption


I use three strategies to find the pivot element.
They are always put to the left.

int leftPivot(int array[], int left, int right) {

    return (array[left]);

int medianOfThreePivot(int array[], int left, int right) {
    int center = (left + right) / 2;

    if (array[left] > array[center])
        swapElement(&array[left], &array[center]);
    if (array[left] > array[right]) 
        swapElement(&array[left], &array[right]);
    if (array[center] > array[right]) 
        swapElement(&array[center], &array[right]);

    swapElement(&array[center], &array[right-1] );
    return (array[left]);

int randomPivot(int array[], int left, int right) {

    int pivot;

    srand ( time(NULL) );
    pivot = left+rand()%(right-left+1);
    swapElement(&array[left], &array[pivot]);

    return (array[left]);

Yeah, i had the same problem... The solution i found to it, that is without using dynamic allocation, is writing all my data down into a separate file.. And then sorting the elements in the file by using functions like seekg() and tellg(). And after which u can read out the median.


Well after tons of research i solved it

It was due to visual studio not allocating enough stack/heap memory.. so it just ran out when it did all the recursive calls on quicksort.

But i downloaded Pelles C and edited the stack reserve to 0x 1600000 .. and now i could handle lists of up to 500k elements in descending order with left pivot element.

This question has already been answered. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.