Click here to Skip to main content
14,972,394 members
Articles / General Programming / Algorithms
Posted 6 Jan 2011


8 bookmarked

Optimizing QuickSort

Rate me:
Please Sign up or sign in to vote.
2.75/5 (4 votes)
6 Jan 2011CPOL2 min read
Some things we can do to make QuickSort more efficient


In productivity, there are two variables which are always a concern: time and space. In terms of computing, these are speed and memory. QuickSort, as the overall fastest sorting algorithm, has had people combing over it for nearly 50 years, so there isn't really much left to do as far as directly increasing its speed. However, there remain several ways that we can optimize it so that it can make much better use of its memory.


Just have a good interest in sorting algorithms, and an understanding of QuickSort.


static void OptimizedQuickSort(ref int[] Arr, int Left, int Right)
    int Pivot;
    Pivot = Q_Sort(ref Arr, Left, Right);
    if(Left < Pivot - 1)
        OptimizedQuickSort(ref Arr, Left, Pivot - 1);
    if(Right > Pivot + 1)
        OptimizedQuickSort(ref Arr, Pivot + 1, Right);

static int Q_Sort(ref int[] Arr, int Left, int Right)
    int Pivot;
    Pivot = Arr[Left];
    while(Left < Right)
        while((Arr[Right] >= Pivot) && (Left < Right))
        if(Left != Right)
            Arr[Left] = Arr[Right];
        while((Arr[Left] <= Pivot) && (Left < Right))
        if(Left != Right)
            Arr[Right] = Arr[Left];
    Arr[Left] = Pivot;
    return Left;

The biggest change I made was to separate QuickSort into two functions, so that, at first glance, it looks sort of like MergeSort. The idea for doing this is that instead of each new recursion copying the same code and using up more memory, it reuses the same code.
NOTE: This code only works properly when running a single thread. If you want to use QuickSort on multiple threads, use the standard version.

As a result of the algorithm being split up, we don't need a Temporary Left and Right variable in Q_Sort, because they are kept back in the original function that calls them, so the only variable we need in Q_Sort is the Pivot.

Next, if you look in the OptimizeQuickSort, you will see that I replaced the:

if(Left < Pivot)   &&    if(Right > Pivot)  


if(Left < Pivot - 1)   &&    if(Right > Pivot + 1)   

My reasoning behind this is that, if there is one variable between Left and Pivot, then that variable must be Greater Than Left. What's more, it must be the only variable that is Less than Pivot that is greater than Left, so there is no reason to sort it. The same thing works for Pivot and Right.


Well, that's really all I've got. Just a few things that I think improve upon QuickSort, at least as far as managing memory. I would like to add that I have seen many other ways to make QuickSort more efficient, but nearly all of those advantages only worked on those languages, taking advantage of its features, whereas I wanted to work on the overall design.

If anyone can see any way to further improve upon what I've done here, or if you think this is a waste of time, let me know.



  • 6th January, 2011: Initial post


This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


About the Author

John Paul Walker
United States United States
No Biography provided

Comments and Discussions

GeneralOther optimisations Pin
jsc4210-Jan-11 4:37
professionaljsc4210-Jan-11 4:37 
GeneralMy vote of 4 Pin
JustDownload29-Jan-11 9:27
MemberJustDownload29-Jan-11 9:27 
General3 percent improvement in benchmark testing Pin
bob169729-Jan-11 3:53
Memberbob169729-Jan-11 3:53 
GeneralMy vote of 3 Pin
Emilio Garavaglia7-Jan-11 6:10
MemberEmilio Garavaglia7-Jan-11 6:10 
GeneralQuicksort Pin
T21026-Jan-11 22:15
MemberT21026-Jan-11 22:15 
GeneralComments Pin
peterchen6-Jan-11 22:08
Memberpeterchen6-Jan-11 22:08 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.