Using Python’s Built-In Sorting Algorithm

Out of curiosity, let’s benchmark Python’s built-in sort() method for arrays. Here’s my benchmarking code for timing the sorting of one million random integers:

	import timeit

	setup_code = '''
	import random

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


	test_code = '''
	array.sort()
	'''

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

Here are my results:

	[0.7919449806213379, 0.7905678749084473, 1.1442229747772217,
	1.0725150108337402, 1.0439801216125488]

Pondering the meaning of this as I climb back into my chair, it appears that it almost always pays to use the sorting algorithm built into the language you’re using. This is way faster than our Mergesort and Quicksort implementations, and even that’s an understatement.

As of this writing, Python uses a sorting algorithm called Timsort, named after Tim Peters, who first implemented it. Timsort uses both merging and Insertion Sort together with some other techniques. I encourage you to check it out.

Now, the reason why a language’s built-in sorting algorithm is so fast isn’t only because it uses Timsort. Whenever any language’s built-in methods are implemented, every optimization trick in the book is used to ensure that the method is as fast as possible. As such, even if a language uses Quicksort under the hood of its built-in sorting algorithm, it’s likely to be faster than a textbook implementation.