Sorting algorithms arrange data in a specific order (usually ascending or descending). They are fundamental to efficient searching, data processing, optimization and many real-world systems.
In this chapter you will learn
A sorting algorithm is stable if it preserves the relative order of elements with equal keys (values).
Example:
Examples:
A sort is in-place if it requires only a constant amount of extra memory: O(1).
These algorithms sort by comparing elements with <, >, or ==.
These algorithms do not compare elements directly.
They can beat the O(n log n) lower bound for special cases (e.g. small integer ranges).
Bubble Sort repeatedly steps through the array, compares adjacent elements, and swaps them if they are in the wrong order. Large values "bubble up" to the end.
| Best | Average | Worst | Space | Stable |
|---|---|---|---|---|
| O(n) | O(n²) | O(n²) | O(1) | Yes |
This implementation includes an optimization to stop early if no swaps occur in a pass.
def bubble_sort(arr):
n = len(arr)
for i in range(n):
# Track if a swap happened (for early exit)
swapped = False
for j in range(n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
if not swapped:
break
return arrSelection Sort repeatedly finds the minimum element from the unsorted part and places it at the beginning.
| Best | Average | Worst | Space | Stable |
|---|---|---|---|---|
| O(n²) | O(n²) | O(n²) | O(1) | No |
Note: This implementation is not stable since it swaps elements.
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_i = i
for j in range(i + 1, n):
if arr[j] < arr[min_i]:
min_i = j
arr[i], arr[min_i] = arr[min_i], arr[i]
return arrInsertion Sort builds the final sorted array one element at a time. It is efficient for small or nearly sorted arrays.
| Best | Average | Worst | Space | Stable |
|---|---|---|---|---|
| O(n) | O(n²) | O(n²) | O(1) | Yes |
This implementation shifts elements to make space for the key element.
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
# Move elements that are greater than key to one position ahead
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arrMerge Sort recursively divides the array into halves, sorts each half, and merges them.
Merge Sort is a divide & conquer algorithm. It splits the array into halves, sorts each half recursively, and then merges them.
Merge Sort has a consistent time complexity of O(n log n) in all cases,
but it requires additional space for merging.
| Best | Average | Worst | Space | Stable |
|---|---|---|---|---|
| O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
This implementation uses recursion to divide and merge the array.
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
# Merge two sorted lists
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
# Add any remaining elements
result.extend(left[i:])
result.extend(right[j:])
return resultQuick Sort is another divide & conquer algorithm and is one of the fastest in practice. It picks a pivot, partitions elements into two groups (less than and greater than pivot), and recursively sorts the partitions.
Quick Sort has an average time complexity of O(n log n),
but degrades to O(n²) in the worst case (e.g., already sorted arrays with poor pivot choice).
| Best | Average | Worst | Space | Stable |
|---|---|---|---|---|
| O(n log n) | O(n log n) | O(n²) | O(log n) | No |
This implementation uses the first element as the pivot.
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[0]
left = [x for x in arr[1:] if x < pivot]
right = [x for x in arr[1:] if x >= pivot]
return quick_sort(left) + [pivot] + quick_sort(right)Heap Sort uses a binary heap data structure to repeatedly extract the minimum (or maximum) element.
Heap Sort has a consistent time complexity of O(n log n) in all cases,
and it sorts in place without needing extra arrays.
| Best | Average | Worst | Space | Stable |
|---|---|---|---|---|
| O(n log n) | O(n log n) | O(n log n) | O(1) | No |
heapq
This implementation uses Python's built-in heapq module for heap operations.
import heapq
def heap_sort(arr):
h = arr[:] # copy to avoid mutating original
heapq.heapify(h) # build min-heap in-place
return [heapq.heappop(h) for _ in range(len(h))]Counting Sort is a linear-time sorting algorithm for integers within a known, limited range. It counts occurrences of each value and then reconstructs the sorted array.
Counting Sort runs in linear time O(n + k), where k is the range of input values.
def counting_sort(arr, max_val):
count = [0] * (max_val + 1)
# Count occurrences
for num in arr:
count[num] += 1
# Build output
output = []
for value, c in enumerate(count):
output.extend([value] * c)
return outputRadix Sort sorts integers digit by digit, starting from the least significant digit (LSD) or most significant digit (MSD). It usually uses a stable sort like Counting Sort as a subroutine.
Radix Sort sorts integers digit by digit, starting from the least significant digit (LSD) or most significant digit (MSD). It usually uses a stable sort like Counting Sort as a subroutine.
O(d × (n + k)), where d is the number of digits and k is the base (e.g., 10).
This implementation uses Counting Sort as a stable subroutine for each digit.
def counting_sort_exp(arr, exp):
output = [0] * len(arr)
count = [0] * 10 # digits 0-9
# Count occurrences of each digit
for num in arr:
index = (num // exp) % 10
count[index] += 1
# Convert to prefix sum
for i in range(1, 10):
count[i] += count[i - 1]
# Build output (stable)
for i in range(len(arr) - 1, -1, -1):
index = (arr[i] // exp) % 10
output[count[index] - 1] = arr[i]
count[index] -= 1
return output
def radix_sort(arr):
if not arr:
return arr
max_val = max(arr)
exp = 1
while max_val // exp > 0:
arr = counting_sort_exp(arr, exp)
exp *= 10
return arrBucket Sort works well for floating-point numbers in a limited range (e.g., [0, 1)). It distributes elements into buckets, sorts each bucket, and then concatenates them.
This implementation assumes input values are in the range [0, 1).
def bucket_sort(arr):
if not arr:
return arr
# Create buckets (for numbers in [0, 1))
buckets = [[] for _ in range(10)]
# Distribute input array values into buckets
for num in arr:
index = int(num * 10) # assumes 0 <= num < 1
buckets[index].append(num)
# Sort each bucket and concatenate
result = []
for bucket in buckets:
bucket.sort() # built-in Timsort
result.extend(bucket)
return resultThis table summarizes the time complexities and stability of various sorting algorithms.
| Algorithm | Best | Average | Worst | Stable |
|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | Yes |
| Selection Sort | O(n²) | O(n²) | O(n²) | No |
| Insertion Sort | O(n) | O(n²) | O(n²) | Yes |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | Yes |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | No |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | No |
| Counting Sort | O(n + k) | O(n + k) | O(n + k) | Yes |
| Radix Sort | O(d(n + k)) | O(d(n + k)) | O(d(n + k)) | Yes |
Python’s built-in sorting uses Timsort, a hybrid of Merge Sort and Insertion Sort. It is:
You can sort lists in place using the sort() method or get a sorted copy using the sorted() function.
# In-place sort
arr = [5, 2, 9, 1]
arr.sort()
print(arr)
# Sorted copy
arr = [5, 2, 9, 1]
sorted_arr = sorted(arr)
print(sorted_arr)The choice of sorting algorithm depends on the specific requirements of your application, such as data size, memory constraints, and whether stability is needed. Here are some guidelines:
For most applications, Python's built-in Timsort is the best choice due to its efficiency and stability.
sort() or sorted() (Timsort).Consider these scenarios:
In this guide, you learned:
Mastering sorting algorithms builds a strong foundation for more advanced topics such as searching, graph algorithms, and optimization problems.