DSA Sorting Algorithms
Sorting puts items in order, such as numbers from small to large or names from A to Z.
Why Sorting Matters
Sorted data is easier to search (binary search), to show (a ranked list of results) and to process (finding duplicates). There are many sorting algorithms; here are the five most important.
Bubble Sort
Compare each pair of neighbours and swap them if they are in the wrong order. After each pass, the biggest remaining item "bubbles" to the end.
Example
def bubble_sort(items):
n = len(items)
for i in range(n - 1):
swapped = False
for j in range(n - 1 - i):
if items[j] > items[j + 1]:
items[j], items[j + 1] = items[j + 1], items[j]
swapped = True
if not swapped:
break
return items
print(bubble_sort([5, 1, 4, 2, 8]))[1, 2, 4, 5, 8]
Simple to understand, but slow: O(n^2). The swapped check stops early if the list is already sorted.
Selection Sort
Find the smallest item and put it first. Then find the smallest of the rest and put it second, and so on.
Example
def selection_sort(items):
n = len(items)
for i in range(n):
smallest = i
for j in range(i + 1, n):
if items[j] < items[smallest]:
smallest = j
items[i], items[smallest] = items[smallest], items[i]
return items
print(selection_sort([64, 25, 12, 22, 11]))[11, 12, 22, 25, 64]
Also O(n^2), but it makes very few swaps.
Insertion Sort
Take items one by one and insert each into its correct place among the items already sorted, like arranging playing cards in your hand.
Example
def insertion_sort(items):
for i in range(1, len(items)):
key = items[i]
j = i - 1
while j >= 0 and items[j] > key:
items[j + 1] = items[j]
j -= 1
items[j + 1] = key
return items
print(insertion_sort([9, 5, 1, 4, 3]))[1, 3, 4, 5, 9]
O(n^2) in general, but very fast, close to O(n), when the list is almost sorted.
Merge Sort
Divide and conquer: split the list in half, sort each half with recursion, then merge the two sorted halves.
Example
def merge_sort(items):
if len(items) <= 1:
return items
mid = len(items) // 2
left = merge_sort(items[:mid])
right = merge_sort(items[mid:])
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))[3, 9, 10, 27, 38, 43, 82]
Always O(n log n), but it needs O(n) extra memory for the merged lists.
Quick Sort
Pick a pivot. Put smaller items to its left and bigger items to its right, then sort both sides the same way.
Example
def quick_sort(items):
if len(items) <= 1:
return items
pivot = items[len(items) // 2]
left = [x for x in items if x < pivot]
middle = [x for x in items if x == pivot]
right = [x for x in items if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
print(quick_sort([33, 10, 55, 71, 29, 10, 4]))[4, 10, 10, 29, 33, 55, 71]
O(n log n) on average and very fast in practice. With very bad pivots it can become O(n^2).
Comparison
| Algorithm | Best | Average | Worst | Extra memory |
|---|---|---|---|---|
| Bubble sort | O(n) | O(n^2) | O(n^2) | O(1) |
| Selection sort | O(n^2) | O(n^2) | O(n^2) | O(1) |
| Insertion sort | O(n) | O(n^2) | O(n^2) | O(1) |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) |
| Quick sort | O(n log n) | O(n log n) | O(n^2) | O(log n) |
In real Python code, use sorted(items) or items.sort(). They use Timsort, a mix of merge sort and insertion sort that runs in O(n log n). Learn the algorithms above to understand how sorting works and to pass interviews.
Example
students = [("Ali", 72), ("Sara", 91), ("Hamza", 85)]
print(sorted(students, key=lambda s: s[1], reverse=True))[('Sara', 91), ('Hamza', 85), ('Ali', 72)]Exercise
Exercise
Which sorting algorithm splits the list in half, sorts each half and then merges them?