Mergesort vs. Quicksort

This entire discussion of benchmarking came about as a result of contrasting Mergesort with Quicksort in the previous chapter, so let’s use benchmarking to see for ourselves whether Quicksort is truly the faster algorithm.

Following is the Quicksort code from Volume 1, Chapter 13:

	class SortableArray:

	def __init__(self, array):
	self.array = array

	def partition(self, left_pointer, right_pointer):
	pivot_index = right_pointer
	pivot = self.array[pivot_index]
	right_pointer -= 1

	while True:

	while self.array[left_pointer] < pivot:
	left_pointer += 1

	while self.array[right_pointer] > pivot:
	right_pointer -= 1

	if left_pointer >= right_pointer:
	break
	else:
	self.array[left_pointer], self.array[right_pointer] = \
	self.array[right_pointer], self.array[left_pointer]
	left_pointer += 1

	self.array[left_pointer], self.array[pivot_index] = \
	self.array[pivot_index], self.array[left_pointer]

	return left_pointer

	def quicksort(self, left_index, right_index):
	if right_index - left_index <= 0:
	return

	pivot_index = self.partition(left_index, right_index)

	self.quicksort(left_index, pivot_index - 1)

	self.quicksort(pivot_index + 1, right_index)

Here is my Quicksort benchmarking code. For this experiment, I’ll time how long it takes to sort one million random integers:

	import timeit

	setup_code = '''
	import random
	import quicksort

	array = []
	for i in range(1_000_000):
	n = random.randint(1, 1_000_000)
	array.append(n)

	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))

Since it’s been a few minutes since benchmarking Mergesort, it’s best to run that again, too. Note that I’m benchmarking our “regular” Mergesort, not the one we optimized using Insertion Sort. Here are my side-by-side results:

	Mergesort:
	[9.667517900466919, 9.65391206741333, 11.16753602027893,
	10.575589895248413, 10.170050144195557]

	Quicksort:
	[5.473771095275879, 5.405587196350098, 5.787222862243652,
	5.61734414100647, 6.785470008850098]

Wow, Quicksort is almost twice as fast. That’s pretty impressive, and pretty much in line with what computer scientists have been telling us. Go computer scientists!

The moral of the story is that although two algorithms may take the same number of Python steps, one can be significantly faster than the other in actual time. Again, this is due to factors under the hood of the computer, such as the number of machine-code steps and spatial locality. These under-the-hood factors may be difficult to predict, and that’s exactly why we use benchmarking to determine the actual-time speed of an algorithm.