Sorting Algorithms in Python
Python makes sorting algorithms easy to read, which is why it is a favourite for learning them. This guide shows clean Python implementations of the most important sorts and explains how Python's own built-in sorted() and list.sort() work under the hood.
The built-in sort
For real code, just use the built-in: sorted(data) returns a new list and data.sort() sorts in place. Both use Tim Sort, are stable, and run in O(n log n). Use the key parameter for custom orderings, e.g. sorted(users, key=lambda u: u.age).
Quick Sort in Python
def quick_sort(a):
if len(a) <= 1:
return a
pivot = a[len(a) // 2]
left = [x for x in a if x < pivot]
mid = [x for x in a if x == pivot]
right = [x for x in a if x > pivot]
return quick_sort(left) + mid + quick_sort(right)This concise version is readable but not in-place; see the Quick Sort guide for the in-place partition scheme.
Merge Sort and Insertion Sort
def insertion_sort(a):
for i in range(1, len(a)):
key = a[i]
j = i - 1
while j >= 0 and a[j] > key:
a[j + 1] = a[j]
j -= 1
a[j + 1] = key
return aInsertion Sort is great for small lists. For larger data use Merge or Quick Sort, or simply the built-in.
Frequently asked questions
What sorting algorithm does Python use? +
Should I implement my own sort in Python? +
See it in motion
Watch this algorithm and 9 others run step by step in our free interactive visualizer.
▶ Launch Visualiser