Difficulty: Advanced
Sorting algorithms arrange elements of a collection in a specific order (ascending or descending). Understanding how different sorting algorithms work, their time complexities, and when to use each one is a cornerstone of computer science and a frequent topic in technical interviews.
Bubble sort is the simplest sorting algorithm. It repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process repeats until no more swaps are needed. While easy to understand, bubble sort has O(n^2) time complexity in the average and worst cases, making it impractical for large datasets. An optimization is to track whether any swaps occurred in a pass; if not, the list is already sorted and we can stop early.
Selection sort works by repeatedly finding the minimum element from the unsorted portion and placing it at the beginning of the unsorted section. It divides the list into a sorted and unsorted region, growing the sorted region one element at a time. Like bubble sort, it has O(n^2) time complexity, but it makes fewer swaps (at most n-1), which can be advantageous when write operations are expensive.
Insertion sort builds the sorted array one element at a time by inserting each new element into its correct position among the previously sorted elements. It is efficient for small datasets and nearly sorted data (O(n) best case). Many real-world sorting implementations, including Python's Timsort, use insertion sort for small sub-arrays because of its low overhead.
Python's built-in sorted() function and the list .sort() method both use Timsort, a hybrid algorithm combining merge sort and insertion sort. Timsort has O(n log n) worst-case time complexity and O(n) best case for nearly sorted data. The key difference: sorted() returns a new list and works on any iterable, while .sort() sorts the list in-place and returns None. Both accept key and reverse parameters for custom sorting behavior.
def bubble_sort(arr):
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
if not swapped:
break
return arr
print(bubble_sort([64, 34, 25, 12, 22, 11, 90]))Each pass bubbles the largest unsorted element to its correct position. The swapped flag enables early termination if the list becomes sorted before all passes complete.
def selection_sort(arr):
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
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
print(selection_sort([29, 10, 14, 37, 13]))Selection sort finds the smallest element in the unsorted portion and swaps it with the first unsorted element. It performs exactly n-1 swaps regardless of input.
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
print(insertion_sort([5, 2, 4, 6, 1, 3]))Insertion sort picks each element and inserts it into the correct position among the already-sorted elements to its left. It is very efficient for nearly sorted data.
numbers = [3, 1, 4, 1, 5, 9, 2, 6]
sorted_new = sorted(numbers)
print(sorted_new)
print(numbers)
numbers.sort(reverse=True)
print(numbers)
words = ["banana", "apple", "cherry"]
print(sorted(words, key=len))sorted() returns a new sorted list without modifying the original. .sort() modifies the list in-place and returns None. Both accept key (a function applied to each element for comparison) and reverse (boolean for descending order).
bubble sort, selection sort, insertion sort, Timsort