Sorting is one of the most fundamental operations in computer science. Understanding different sorting algorithms helps you choose the right one for different scenarios and is essential for technical interviews.
In this guide, we’ll explore comparison-based sorting algorithms (O(n log n)) and linear-time sorting algorithms (O(n)).
Comparison of Sorting Algorithms
┌─────────────────────────────────────────────────────────────┐
│ Sorting Algorithm Comparison │
│ │
│ Algorithm │ Best │ Average │ Worst │ Stable │
│ ──────────────┼───────────┼──────────┼──────────┼────────│
│ Bubble Sort │ O(n) │ O(n²) │ O(n²) │ Yes │
│ Selection │ O(n²) │ O(n²) │ O(n²) │ No │
│ Insertion │ O(n) │ O(n²) │ O(n²) │ Yes │
│ Merge Sort │ O(n log n)│ O(n log n)│ O(n log n)│ Yes │
│ Heap Sort │ O(n log n)│ O(n log n)│ O(n log n)│ No │
│ Quick Sort │ O(n log n)│ O(n log n)│ O(n²) │ No │
│ Tim Sort │ O(n) │ O(n log n)│ O(n log n)│ Yes │
│ ──────────────┼───────────┼──────────┼──────────┼────────│
│ Counting │ O(n + k) │ O(n + k) │ O(n + k) │ Yes │
│ Radix │ O(nk) │ O(nk) │ O(nk) │ Yes │
│ Bucket │ O(n + k) │ O(n + k) │ O(n²) │ Yes │
│ │
│ k = range of input, n = number of elements │
└─────────────────────────────────────────────────────────────┘
Comparison-Based Sorts
Bubble Sort
def bubble_sort(arr):
"""Simple but inefficient - O(n²)"""
n = len(arr)
for i in range(n):
swapped = False
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
# Optimization: if no swaps, array is sorted
if not swapped:
break
return arr
def bubble_sort_optimized(arr):
"""With early termination and tracking"""
n = len(arr)
left = 0
right = n - 1
while left < right:
new_right = 0
# Forward pass
for j in range(left, right):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
new_right = j
right = new_right
if right <= left:
break
# Backward pass
new_left = right
for j in range(right, left, -1):
if arr[j - 1] > arr[j]:
arr[j], arr[j - 1] = arr[j - 1], arr[j]
new_left = j - 1
left = new_left + 1
return arr
Selection Sort
def selection_sort(arr):
"""O(n²) but fewer writes than bubble sort"""
n = len(arr)
for i in range(n):
# Find minimum in remaining unsorted portion
min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
# Swap
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
def selection_sort_stable(arr):
"""Stable version - maintains relative order"""
n = len(arr)
for i in range(n):
min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
# Shift elements instead of swapping
key = arr[min_idx]
j = min_idx - 1
while j >= i and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
Insertion Sort
def insertion_sort(arr):
"""O(n) for nearly sorted, O(n²) worst"""
n = len(arr)
for i in range(1, n):
key = arr[i]
j = i - 1
# Move elements greater than key
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
def insertion_sort_binary(arr):
"""Binary search to find position - O(n²) but fewer comparisons"""
n = len(arr)
for i in range(1, n):
key = arr[i]
# Binary search
left, right = 0, i - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] > key:
right = mid - 1
else:
left = mid + 1
# Shift
j = i - 1
while j >= left:
arr[j + 1] = arr[j]
j -= 1
arr[left] = key
return arr
Merge Sort
def merge_sort(arr):
"""O(n log n) - Divide and conquer"""
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):
"""Merge two sorted arrays"""
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
def merge_sort_inplace(arr):
"""In-place merge sort"""
_merge_sort_inplace(arr, 0, len(arr) - 1)
def _merge_sort_inplace(arr, left, right):
if left < right:
mid = (left + right) // 2
_merge_sort_inplace(arr, left, mid)
_merge_sort_inplace(arr, mid + 1, right)
_merge_inplace(arr, left, mid, right)
def _merge_inplace(arr, left, mid, right):
"""In-place merge"""
left_copy = arr[left:mid + 1]
right_copy = arr[mid + 1:right + 1]
i = j = 0
k = left
while i < len(left_copy) and j < len(right_copy):
if left_copy[i] <= right_copy[j]:
arr[k] = left_copy[i]
i += 1
else:
arr[k] = right_copy[j]
j += 1
k += 1
while i < len(left_copy):
arr[k] = left_copy[i]
i += 1
k += 1
while j < len(right_copy):
arr[k] = right_copy[j]
j += 1
k += 1
Quick Sort
def quicksort(arr):
"""O(n log n) average, O(n²) worst"""
_quicksort(arr, 0, len(arr) - 1)
return arr
def _quicksort(arr, low, high):
if low < high:
pivot_idx = partition(arr, low, high)
_quicksort(arr, low, pivot_idx - 1)
_quicksort(arr, pivot_idx + 1, high)
def partition(arr, low, high):
"""Lomuto partition scheme"""
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
def quicksort_hoare(arr):
"""Hoare partition - often faster"""
_quicksort_hoare(arr, 0, len(arr) - 1)
return arr
def _quicksort_hoare(arr, low, high):
if low < high:
pivot_idx = partition_hoare(arr, low, high)
_quicksort_hoare(arr, low, pivot_idx)
_quicksort_hoare(arr, pivot_idx + 1, high)
def partition_hoare(arr, low, high):
"""Hoare partition"""
pivot = arr[low]
i = low - 1
j = high + 1
while True:
do
i += 1
while arr[i] < pivot
do
j -= 1
while arr[j] > pivot
if i >= j:
return j
arr[i], arr[j] = arr[j], arr[i]
def quicksort_three_way(arr):
"""Dutch National Flag partition - handles duplicates well"""
_three_way_quicksort(arr, 0, len(arr) - 1)
return arr
def _three_way_quicksort(arr, low, high):
if low >= high:
return
lt = low # arr[low..lt-1] < pivot
gt = high # arr[gt+1..high] > pivot
i = low # arr[lt..i-1] == pivot
pivot = arr[low]
while i <= gt:
if arr[i] < pivot:
arr[lt], arr[i] = arr[i], arr[lt]
lt += 1
i += 1
elif arr[i] > pivot:
arr[i], arr[gt] = arr[gt], arr[i]
gt -= 1
else:
i += 1
_three_way_quicksort(arr, low, lt - 1)
_three_way_quicksort(arr, gt + 1, high)
Heap Sort
def heap_sort(arr):
"""O(n log n) - in-place, not stable"""
n = len(arr)
# Build max heap
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
# Extract elements
for i in range(n - 1, 0, -1):
arr[0], arr[i] = arr[i], arr[0]
heapify(arr, i, 0)
return arr
def heapify(arr, n, i):
"""Heapify subtree rooted at index i"""
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and arr[left] > arr[largest]:
largest = left
if right < n and arr[right] > arr[largest]:
largest = right
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
# Using heapq
import heapq
def heap_sort_heapq(arr):
"""Using Python's heapq"""
heapq.heapify(arr)
return [heapq.heappop(arr) for _ in range(len(arr))]
Tim Sort (Python’s Built-in)
# Python's sorted() uses Tim Sort
# It's a hybrid of merge sort and insertion sort
# Tim Sort characteristics:
# - O(n) for already sorted data
# - O(n log n) worst case
# - Stable
# - Adaptive
# Usage
sorted_list = sorted([3, 1, 4, 1, 5, 9, 2, 6])
# Returns [1, 1, 2, 3, 4, 5, 6, 9]
# In-place
arr = [3, 1, 4, 1, 5, 9, 2, 6]
arr.sort() # Modifies in place
Linear-Time Sorts
Counting Sort
def counting_sort(arr):
"""O(n + k) where k is range - works for integers"""
if not arr:
return arr
# Find range
min_val = min(arr)
max_val = max(arr)
range_size = max_val - min_val + 1
# Count occurrences
count = [0] * range_size
for num in arr:
count[num - min_val] += 1
# Prefix sum (cumulative count)
for i in range(1, range_size):
count[i] += count[i - 1]
# Build output array
output = [0] * len(arr)
for num in reversed(arr): # Reverse for stability
idx = num - min_val
count[idx] -= 1
output[count[idx]] = num
return output
def counting_sort_by_digit(arr, exp):
"""Counting sort for specific digit"""
n = len(arr)
output = [0] * n
count = [0] * 10
# Count occurrences of digits
for num in arr:
digit = (num // exp) % 10
count[digit] += 1
# Cumulative count
for i in range(1, 10):
count[i] += count[i - 1]
# Build output (right to left for stability)
for i in range(n - 1, -1, -1):
digit = (arr[i] // exp) % 10
count[digit] -= 1
output[count[digit]] = arr[i]
return output
Radix Sort
def radix_sort(arr):
"""O(nk) where k is number of digits"""
if not arr:
return arr
# Find maximum to determine digits
max_val = max(arr)
# Sort by each digit (least significant to most)
exp = 1
while max_val // exp > 0:
arr = counting_sort_by_digit(arr, exp)
exp *= 10
return arr
def radix_sort_negative(arr):
"""Handles negative numbers"""
if not arr:
return arr
negatives = [-x for x in arr if x < 0]
positives = [x for x in arr if x >= 0]
# Sort each part
negatives = radix_sort(negatives)
positives = radix_sort(positives)
# Combine: negatives (reversed) + positives
return [-x for x in reversed(negatives)] + positives
Bucket Sort
def bucket_sort(arr):
"""O(n + k) average - works well for uniformly distributed data"""
if not arr:
return arr
n = len(arr)
min_val = min(arr)
max_val = max(arr)
if min_val == max_val:
return arr
# Create buckets
bucket_count = n
buckets = [[] for _ in range(bucket_count)]
range_size = (max_val - min_val) / bucket_count
# Distribute elements
for num in arr:
bucket_idx = min(
int((num - min_val) / range_size),
bucket_count - 1
)
buckets[bucket_idx].append(num)
# Sort each bucket and concatenate
result = []
for bucket in buckets:
if bucket:
bucket.sort() # Can use any sort here
result.extend(bucket)
return result
def bucket_sort_with_insertion(arr):
"""Using insertion sort for small buckets"""
n = len(arr)
if n <= 1:
return arr
min_val = min(arr)
max_val = max(arr)
bucket_count = n
buckets = [[] for _ in range(bucket_count)]
# Distribute
range_size = (max_val - min_val) / bucket_count or 1
for num in arr:
idx = int((num - min_val) / range_size)
buckets[idx].append(num)
# Sort each bucket with insertion sort
result = []
for bucket in buckets:
for i in range(1, len(bucket)):
key = bucket[i]
j = i - 1
while j >= 0 and bucket[j] > key:
bucket[j + 1] = bucket[j]
j -= 1
bucket[j + 1] = key
result.extend(bucket)
return result
Choosing a Sorting Algorithm
# When to use which algorithm
def choose_sort(arr):
"""
Algorithm Selection Guide:
"""
use_cases = {
"small_arrays": {
"algorithm": "Insertion Sort",
"reason": "Low overhead, O(n) for sorted data"
},
"nearly_sorted": {
"algorithm": "Insertion Sort / Tim Sort",
"reason": "Adaptive, performs better"
},
"general_purpose": {
"algorithm": "Tim Sort (sorted())",
"reason": "Python's default, optimized for real data"
},
"memory_constrained": {
"algorithm": "Heap Sort",
"reason": "In-place O(1) extra space"
},
"stable_sort_needed": {
"algorithm": "Merge Sort / Tim Sort",
"reason": "Maintains relative order"
},
"integers_bounded": {
"algorithm": "Counting / Radix Sort",
"reason": "O(n) linear time"
},
"duplicates_many": {
"algorithm": "3-way Quicksort",
"reason": "Handles duplicates efficiently"
}
}
Testing Sorting Algorithms
import random
import time
def test_sort(sort_func, size=10000):
"""Test sorting algorithm"""
# Random
arr = list(range(size))
random.shuffle(arr)
start = time.time()
result = sort_func(arr.copy())
random_time = time.time() - start
# Sorted
arr = list(range(size))
start = time.time()
result = sort_func(arr.copy())
sorted_time = time.time() - start
# Reverse sorted
arr = list(range(size, 0, -1))
start = time.time()
result = sort_func(arr.copy())
reverse_time = time.time() - start
return {
"random": random_time,
"sorted": sorted_time,
"reverse": reverse_time
}
# Example usage
# results = test_sort(quicksort)
# print(f"Quick Sort: {results}")
Conclusion
Sorting algorithms are fundamental to computer science:
- Comparison sorts: O(n log n) is optimal for comparison-based sorting
- Quick sort: Fastest in practice but not stable
- Merge sort: Stable, good for linked lists
- Heap sort: In-place but not stable
- Linear sorts: O(n) when data meets specific conditions
Python’s sorted() and list.sort() use Tim Sort, which is optimized for real-world data.
Related Articles
- Arrays and Strings: Fundamentals
- Linked Lists: Implementation and Practical Use Cases
- Dynamic Programming Fundamentals
Comments