Quicksorting a Sorted Array

In the previous chapter, it appeared that possibly the most significant advantage of Mergesort over Quicksort is that Mergesort runs at O(N log N) in all scenarios, while Quicksort is O(N²) in the worst case. Again, for Quicksort, the worst case is an array that’s already sorted.

It would be nice to see how this plays out in actual time, so let’s benchmark it. Here’s our code for benchmarking Quicksort on a sorted array of size 10,000:

	import timeit
	setup_code = '''
	import quicksort

	array = []
	for i in range(10000):
	array.insert(0, i)
	sortable_array = quicksort.SortableArray(array)
	'''

	test_code = '''
	sortable_array.quicksort(0, len(array) - 1)
	'''

	print(timeit.repeat(stmt=test_code, setup=setup_code, repeat=5, number=1))

Welp, I don’t get any results at all. Instead, I receive this error message:

RuntimeError: maximum recursion depth exceeded

This makes sense, come to think of it, since Quicksort calls itself recursively and the call stack doesn’t unwind until we reach the base case of the left and right pointers meeting. And when the array is sorted, this won’t happen until we’re thousands of calls deep.

To get the code to complete on my computer, I have to change the array size to a paltry 900. When I benchmark both Mergesort and Quicksort on a sorted array of this size, I get the following results:

	Mergesort:
	[0.0037310123443603516, 0.0049169063568115234, 0.003873109817504883,
	0.0034210681915283203, 0.0033721923828125]

	Quicksort:
	[0.04238104820251465, 0.04095888137817383, 0.06446003913879395,
	0.087677001953125, 0.06192493438720703]

Indeed, Mergesort in this scenario is at least 10 times faster.

This confirms what we saw earlier: while Quicksort is faster than Mergesort in the average case, Mergesort is faster than Quicksort in a worst-case scenario. This would seem to be Mergesort’s redeeming quality.

But there’s bad news for Team Mergesort. There’s an optimization for Quicksort that will ensure that it, too, will not slow down in a worst-case scenario, which thereby eliminates Mergesort’s signature advantage. In the next chapter, we’ll explore this optimization, which in turn will unlock an entire class of algorithms and data structures that will become the foundation for the rest of this book.