Merge sort versus quick sort performance

I have implemented merge sort and quick sort using C (GCC 4.4.3 on Ubuntu 10.04 running on a 4 GB RAM laptop with an Intel DUO CPU at 2GHz) and I wanted to compare the performance of the two algorithms.

The prototypes of the sorting functions are:

void merge_sort(const char **lines, int start, int end);

void quick_sort(const char **lines, int start, int end);

i.e. both take an array of pointers to strings and sort the elements with index i : start <= i <= end.

I have produced some files containing random strings with length on average 4.5 characters. The test files range from 100 lines to 10000000 lines.

I was a bit surprised by the results because, even though I know that merge sort has complexity O(n log(n)) while quick sort is O(n^2), I have often read that on average quick sort should be as fast as merge sort. However, my results are the following.

• Up to 10000 strings, both algorithms perform equally well. For 10000 strings, both require about 0.007 seconds.
• For 100000 strings, merge sort is slightly faster with 0.095 s against 0.121 s.
• For 1000000 strings merge sort takes 1.287 s against 5.233 s of quick sort.
• For 5000000 strings merge sort takes 7.582 s against 118.240 s of quick sort.
• For 10000000 strings merge sort takes 16.305 s against 1202.918 s of quick sort.

So my question is: are my results as expected, meaning that quick sort is comparable in speed to merge sort for small inputs but, as the size of the input data grows, the fact that its complexity is quadratic will become evident?

Here is a sketch of what I did. In the merge sort implementation, the partitioning consists in calling merge sort recursively, i.e.

merge_sort(lines, start, (start + end) / 2);
merge_sort(lines, 1 + (start + end) / 2, end);

Merging of the two sorted sub-array is performed by reading the data from the array lines and writing it to a global temporary array of pointers (this global array is allocate only once). After each merge the pointers are copied back to the original array. So the strings are stored once but I need twice as much memory for the pointers.

For quick sort, the partition function chooses the last element of the array to sort as the pivot and scans the previous elements in one loop. After it has produced a partition of the type

start ... {elements <= pivot} ... pivotIndex ... {elements > pivot} ... end

it calls itself recursively:

quick_sort(lines, start,          pivotIndex - 1);
quick_sort(lines, pivotIndex + 1, end);

Note that this quick sort implementation sorts the array in-place and does not require additional memory, therefore it is more memory efficient than the merge sort implementation.

So my question is: is there a better way to implement quick sort that is worthwhile trying out? If I improve the quick sort implementation and perform more tests on different data sets (computing the average of the running times on different data sets) can I expect a better performance of quick sort wrt merge sort?

EDIT

My implementation is in-place and is based on the pseudo-code I have found on wikipedia in Section In-place version:

function partition(array, 'left', 'right', 'pivotIndex')

where I choose the last element in the range to be sorted as a pivot, i.e. pivotIndex := right. I have checked the code over and over again and it seems correct to me. In order to rule out the case that I am using the wrong implementation I have uploaded the source code on github (in case you would like to take a look at it).

Your answers seem to suggest that I am using the wrong test data. I will look into it and try out different test data sets. I will report as soon as I have some results.

• you hit a poor set for quick sort or choose a poor pivot method it seems Apr 26 '12 at 20:36
• Quicksort is normally O(n log(n)), just like mergesort. It is only O(n^2) under worst-case conditions. See en.wikipedia.org/wiki/Quicksort Apr 26 '12 at 20:37
• @Robert Harvey: So should I use a large set of random data and run many tests? Then I should have O(n log(n)) on average. Apr 26 '12 at 20:40
• @Giorgio: You should use a data set that doesn't degrade to O(n^2), and is large enough to identify any performance differences between quicksort and mergesort (assuming your quicksort algorithm is correct). The Wikipedia article goes over all these issues in detail, including the use of randomized pivots that guarantee that any source dataset will result in O(n log(n)) performance. Apr 26 '12 at 20:42
• If your strings are an average of 4.5 characters long. Then on a dataset with 10,000,000 strings there will be a lot of duplicate strings. Try using random strings with an average of at least 8 (or preferable more) characters. Nov 25 '14 at 13:34

If you look at your code for swapping you:

// If current element is lower than pivot
// then swap it with the element at store_index
// and move the store_index to the right.

But, ~50% of the time that string you just swapped needs to be moved back, which is why faster merge sorts work from both ends at the same time.

Next if you check to see if the first and last elements are the same before doing each of the recursive call you avoid wasting time calling a function only to quickly exit it. This happens 10000000 in your final test which does add noticeable amounts of time.

Use,

if (pivot_index -1 > start) quick_sort(lines, start, pivot_index - 1);

if (pivot_index + 1 < end) quick_sort(lines, pivot_index + 1, end);

You still want an outer function to do an initial if (start < end) but that only needs to happen once so that function can just call an unsafe version of your code without that outer comparison.

Also, picking a random pivot tends to avoid N^2 worst case results, but it's probably not a big deal with your random data set.

Finally, the hidden problem is QuickSort is comparing strings in ever smaller buckets that are ever closer together,

(Edit: So, AAAAA, AAAAB, AAAAC, AAAAD then AAAAA, AAAAB. So, strcmp needs to step though a lot of A's before looking the useful parts of the strings.)

but with Merge sort you look at the smallest buckets first while they are vary random. Mergsorts final passes do compare a lot of strings close to each other, but it's less of an issue then. One way to make Quick sorts faster for strings is to compare the first digits of the outer strings and if there the same ignore them when doing the inner comparisons, but you have to be careful that all strings have enough digits that your not skipping past the null terminator.

are my results as expected?

Merge sort has the following performance characteristics:

• Best case: O(n log n)
• Average case: O(n log n)
• Worst case: O(n log n)

Quicksort has the following performance characteristics:

• Best case: O(n log n)
• Average case: O(n log n)
• Worst case: O(n^2)

Remember: Big-O Notation states the asymptotic bounds ignoring constant factors.

Quicksort has best-case performance when the pivot elements it chooses tend evenly to partition sub-ranges. It has a worst-case quadratic performance when the the opposite holds, such as when the input is sorted in reverse, or nearly sorted in reverse. There are many varieties of quicksort and they vary, in part, in how they choose pivot elements.

Merge sort performance is much more constrained and predictable than the performance of quicksort. The price for that reliability is that the average case of merge sort is slower than the average case of quicksort because the constant factor of merge sort is larger. However, this constant factor greatly depends on the particular details of the implementation. A good merge sort implementation will have better average performance than a poor quicksort implementation.

• You can check my quick sort implementation here: gist.github.com/2503116. Jun 28 '12 at 5:18
• " Quicksort has a best-case linear performance when the input is sorted, or nearly sorted." - actually, this depends on how the pivot element is chosen. The question states that the implementation tested picks an element from the edge of the range being sorted as pivot; this results in worst case performance for pre-sorted lists. See stackoverflow.com/questions/4019528/quick-sort-worst-case Nov 25 '14 at 19:35
• quick sort doesn't have a best case performance of O(n). the best case occurs when you divide the input array in two almost equal length partitions. which takes O(nlgn) time. Mar 10 '18 at 14:28
• @Jules - Fixed. Apr 12 '18 at 6:18
• @mightyWOZ - Fixed. Apr 12 '18 at 6:18

To try to put this in perspective, let's consider what you can expect from the standard library. To get an idea, I wrote this in C++:

#include <iostream>
#include <algorithm>
#include <vector>
#include <iterator>
#include <string>
#include <time.h>

std::string gen_random() {
size_t len = rand() % 25 + 5;

std::string x;

std::generate_n(std::back_inserter(x), len, rand);
return x;
}

static const int num = 10000000;

int main(){
std::vector<std::string> strings;

std::generate_n(std::back_inserter(strings), num, gen_random);

clock_t start = clock();
std::sort(strings.begin(), strings.end());
clock_t ticks = clock() - start;

std::cout << ticks / (double)CLOCKS_PER_SEC;

return 0;
}

This generates and then sorts the specified number of strings (each between 5 and 30 characters long). On my machine (which is probably somewhat slower than yours) I'm getting a time of ~14 seconds for the sort, which I'd guess is implemented as an Introsort. In the normal case, I'd expect pretty much the same performance from Introsort as Quicksort.

Bottom line: the result you're getting for merge sort is fairly reasonable, but the result you're getting from Quicksort indicates that your implementation has a serious problem.

• I also believe it must have a problem: that's why I asked. My merge sort implementation is comparable to (only slightly slower than) the built-in sort provided by the C library. Apr 26 '12 at 21:00
• I have read about Introsort (en.wikipedia.org/wiki/Introsort). I guess Introsort is better than Quicksort, otherwise there would be no need to invent it (it uses Quicksort but switches to Heapsort if it sees that Quicksort is not doing well enough). So maybe the cases in which Quicksort's performance degrades are not very rare. Apr 28 '12 at 18:52

Your result is most definitely not expected. In fact, quicksort is used because it tends to be quite a bit faster than mergesort in the average case, i.e. if quicksort doesn't degenerate due to badly chosen pivot elements.

This caveat also hints towards the first thing you should try: choose the pivot element for quicksort randomly, thereby eliminating problems with (partially) presorted data. "tuned" quicksorts will even choose 3 or 5 random elements and take the median for the early runs, since the choice of pivot has a disproportional impact there.

And of course it could be that your implementation of quicksort is simply flawed (it's more difficult to implement really correctly than it sounds).

• Thanks for the hints. If the data is random, taking as the pivot the last element of the array should be equivalent to taking any other element, or am I wrong? Anyway, do you know where I can find a good implementation of quick sort on the internet? Then I could copy the code and test with that implementation. Apr 26 '12 at 20:38
• I could paste the implementation, I did not in order not to make the question too long. Apr 26 '12 at 20:41
• @Giorgio: yes, if the data is random, taking the last element is fine - buy why rely on that? As for finding a good implementation, there's this thing called Google... Apr 26 '12 at 20:42
• @Giorgio: you could put it on pastebin or gist.github.com and link to it. Another thing to try: run it on a small set of data in debug mode to see what exactly is happening and whether it works the way it should. Apr 26 '12 at 20:45
• gist.github.com/2503116 Apr 26 '12 at 20:55

I will agree with Michael; Quicksort is difficult to implement correctly. Back when I was in college writing my final exam (a comparison of sorting algorithms) my QuickSort implementation managed to blue-screen a Windows NT computer (it didn't cause a GPF; it BSODed).

The biggest problem I generally encounter when quicksorting is pivot selection. Remember that QuickSort's Achilles' heel is pretty common; a near-sorted list. For that reason, proper pivot selection is crucial despite the extra complexity. Even something so simple as picking the middle element of the subarray is generally better than picking at either end; for the two most common cases of a near-sorted list and a truly random list, this will generally produce a good result. Median-of-3 is even better.

Another thing to check is that you have an intelligent "base case". A partition of 2 elements can be sorted trivially (are they in order? if not, swap em), so pivoting a 2-element array in order to reach the base case of zero or one elements is wasteful.

One more thing is to ensure your algorithm is "in-place" (a major advantage of the "intuitive" QuickSort over the "intuitive" MergeSort; allocating memory is expensive), and that you aren't trying to keep the pivot in between the two halves while you're pivoting. Choose your pivot, swap it with the last element, then work in from the left looking for a "big" element, and then from the right looking for a "small" element; swap and continue until a "big" value is found without a "small" value on its right to swap it with (swap it with the pivot at the last element and recurse). This prevents unneeded swapping to keep the pivot in the "middle" of the two halves.

• Both algorithms are in place. Merge sort needs an extra array of pointers to which the original pointers are copied during merge. This global array is only allocated once at the beginning. Otherwise there is no extra allocation / deallocation going on in either of the two implementations. Apr 27 '12 at 5:07
• @Giorgio: In scenarios where data items are large but stored sequentially and one would want to produce a sorted list of pointers, the "extra" allocation required for merge sort would be required no matter what kind of sort one was using. Further, if data items are large but keys are small, sorting a list of pointers may be much more efficient than swapping around data items, since swapping two data items would require reading both of them fully into cache, while inspecting keys and swapping pointers wouldn't. Nov 4 '20 at 18:32

What happens to Merge sort and Quick sort when every element in the array is exactly the same? Can you solve this problem or this 'edge' case keep their running times the same? Who's performance is better?

What if the data is completely random? Who's performance is better?

So my question is: is there a better way to implement quick sort that is worthwhile trying out?

Have you considered running Insertion Sort within Quick sort when your arrays are < 100 Elements? What value is most efficient to start using Insertion Sort?

How the pivot is chosen is key to Quick Sorts run time. How are you choosing the pivot? Which way is better?

There are actually two ways to implement Quick sort, have you discovered both?

I think you will be well served to think about these questions.

• The input data is randomly generated lists of strings. I have also implemented a variation in which I use insertion sort for small subarrays (10 elements), pick the pivot as the median of first, middle, and last element, and fall back to heap sort when the recursion depth exceeds a certain threshold. In this way I get much better performance (comparable to merge sort), but this is no longer quick sort (AFAIK quick sort + heap sort is called intro sort). Jun 28 '12 at 5:15

Note that the pseudo-code in wiki is not practical. It is written to undestand.
If an array is [0,0,0,1] pivot is 1 and other elements are less than the pivot,
then swapping(t <-- a, a <-- b, b <--t) works as t <-- a, a <-- a, a <-- t.
In this case swapping works nothing.
If an array is [4,2,1,3] then [4,2,1,3] --> [2,4,1,3] --> [2,1,4,3] --> [2,1,3,4].
In this case '4' moves like in bubble sort.

I suggest a new pseudo-code.

quicksort(A, i, k)
if i < k
p := partition(A, i, k)
quicksort(A, i, p - 1)
quicksort(A, p + 1, k)

partition(array, left, right)
hole := choosePivot(Array, left, right)
pivot := array[hole]        // dig a hole
array[hole] := array[right]
hole := right               // move the hole
while left < hole
if array[left] >= pivot
array[hole] := array[left]
hole := left
while right > hole
if array[right] < pivot
array[hole] := array[right]
hole := right
right := right - 1
left := left + 1
array[hole] := pivot        // bury the hole
return hole

Performance comparison is difficult, because it depends on some factors.

1. Implementation
Good code run fast, ugly code run slow, you know.
2. Data size
a. Size of array element.
b. Whole array size exceed a cache memory or not.
c. Whole array size exceed a main memory or not.
3. Data structure
a. An array is stored in a continuous memory as C language.
b. An array consist of pointers to a continuous memory.
c. Pointer is gotten by malloc(3) or "new" operator.
If random number is used then ESD(estimated standard deviation) of processing time is 5%. Not used then 2%. I researched.
5. OS, H/W
Linux/Unix, microsoft windows is multi-task OS. Program is often interrupted.
Many core CPU is better. Test before GUI login is better. Single-task OS is better.

Example: N=100000, 32 byte/element, pivot is a middle element, strcmp(3), continuous memory

qsort_middle()  usec = 522870   call = 999999   compare = 28048465  copy = 15404514
merge_sort()    usec = 533722   call = 999999   compare = 18673585  copy = 19673584

Source C programs and scripts are posted in github. Thre is various quicksort and merge sort.

You are not calling the standard library qsort (or the standard C++ sort) function. What you are calling are two random functions written by some random person who is more or less clever, and that will be reflected in the performance. You are not comparing the performance of two algorithms, you are comparing the performance of two random implementations.

Usually the best thing to do is to use what most people are using, in this case calling qsort. Which you can assume will sort things as fast as it can. Since sorting is so essential, the qsort implementation is unlikely to be plain quicksort, and even less likely to be an implementation of plain quicksort with obvious performance problems (like the quick_sort function that you used).

If you are lucky, qsort will for example sort sorted arrays in linear time, and almost sorted arrays in close to linear time.

• The whole point of my exercise was to understand sorting algorithms and their performance, not to pick a library function to do sorting (I do that for production code, for that matter). Of course, if I have implemented them wrong my results will be wrong. Apr 13 '18 at 12:08