Sorting is the process of arranging a collection of elements in a meaningful order, typically ascending or descending. It is one of the most fundamental operations in computer science because sorted data is far easier to search, display and analyse. A student mark list sorted by roll number, a directory sorted by name, and a price list sorted by cost are all everyday examples of sorted data. Almost every database system and search engine relies heavily on sorting routines.
Many algorithms exist to sort data, and they differ in how they partition, compare and rearrange the elements. This chapter introduces the most commonly taught algorithms: Bubble Sort, Selection Sort, Insertion Sort and the divide-and-conquer Merge Sort. For each algorithm, the chapter explains the underlying idea, gives a step-by-step example, provides a Python implementation, and analyses time and space complexity. Sorting questions appear in the board examination both as short traces (showing the list after each pass) and as 3-mark code writing and complexity questions.
An important theme throughout the chapter is complexity. Sorting a list of n elements requires at least n log n comparisons for comparison-based methods in the best design, and simple algorithms such as bubble and selection sort run in O(n^2) time. Understanding these trade-offs is central to choosing the right algorithm for a given problem, and it connects directly to the later chapter on the idea of efficiency.
Bubble sort repeatedly compares adjacent elements and swaps them if they are in the wrong order. After each complete pass, the largest remaining element "bubbles up" to its correct position at the end of the list. The algorithm performs n-1 passes; in each pass it compares adjacent pairs and needs at most n-1 comparisons.
def bubble_sort(lst):
n = len(lst)
for i in range(n - 1):
for j in range(n - 1 - i):
if lst[j] > lst[j + 1]:
lst[j], lst[j + 1] = lst[j + 1], lst[j]
return lst
print(bubble_sort([64, 34, 25, 12, 22, 11, 90]))
The inner loop bound n - 1 - i is important: after each pass, the largest i+1 elements are already in their final positions at the end, so they need not be compared again. For the list [5, 1, 4, 2], the first pass compares (5,1), swaps; (5,4), swaps; (5,2), swaps, giving [1, 4, 2, 5]. The second pass compares (1,4) and (4,2), swapping the latter, giving [1, 2, 4, 5].
If a complete pass makes no swaps, the list is already sorted and further passes are unnecessary. An added flag can terminate the algorithm early.
def bubble_sort_optimised(lst):
n = len(lst)
for i in range(n - 1):
swapped = False
for j in range(n - 1 - i):
if lst[j] > lst[j + 1]:
lst[j], lst[j + 1] = lst[j + 1], lst[j]
swapped = True
if not swapped:
break
return lst
The worst-case and average-case time complexity is O(n^2) because there are roughly n passes and n comparisons each. The best case (already sorted list, with the optimisation) is O(n). The space complexity is O(1) since sorting happens in place.
Selection sort finds the smallest element in the unsorted portion of the list and swaps it with the first unsorted position. It repeats this until the whole list is sorted. The algorithm makes the same number of comparisons every run, regardless of the initial order, so its time complexity is always O(n^2), but it makes at most n-1 swaps, which is fewer than bubble sort.
def selection_sort(lst):
n = len(lst)
for i in range(n - 1):
min_index = i
for j in range(i + 1, n):
if lst[j] < lst[min_index]:
min_index = j
lst[i], lst[min_index] = lst[min_index], lst[i]
return lst
print(selection_sort([29, 10, 14, 37, 13]))
In the first pass, the algorithm scans [29, 10, 14, 37, 13], finds the minimum 10 at index 1, and swaps it with the element at index 0, giving [10, 29, 14, 37, 13]. The next pass scans [29, 14, 37, 13], finds 13, and swaps it into position 1, giving [10, 13, 14, 37, 29].
Selection sort performs the minimum number of swaps among the simple sorting algorithms: at most n-1 swaps, one per position except the last. This makes it attractive when writing to memory is expensive.
Insertion sort builds the sorted list one element at a time. It takes each element and inserts it into its correct position among the already-sorted elements to its left, shifting the larger elements right to make room. It is analogous to arranging playing cards in hand.
def insertion_sort(lst):
for i in range(1, len(lst)):
key = lst[i]
j = i - 1
while j >= 0 and lst[j] > key:
lst[j + 1] = lst[j]
j -= 1
lst[j + 1] = key
return lst
print(insertion_sort([12, 11, 13, 5, 6]))
For the list [12, 11, 13, 5, 6]: key=11 is inserted before 12 giving [11, 12, 13, 5, 6]; key=13 stays; key=5 shifts everything right, giving [5, 11, 12, 13, 6]; finally key=6 gives the sorted list [5, 6, 11, 12, 13].
The worst-case and average-case time complexity is O(n^2), but the best case for an already-sorted list is O(n) because the while loop exits immediately. Insertion sort is stable, in-place and efficient for small or nearly sorted lists.
Merge sort is a divide-and-conquer algorithm. It divides the list into two halves, recursively sorts each half, and then merges the two sorted halves into one sorted list. The merging step compares the front elements of the two halves and places the smaller into the result, running in O(n) time.
def merge_sort(lst):
if len(lst) <= 1:
return lst
mid = len(lst) // 2
left = merge_sort(lst[:mid])
right = merge_sort(lst[mid:])
return merge(left, right)
def merge(left, right):
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]))
Merge sort always divides the list into two halves, so its time complexity is O(n log n) in the best, average and worst cases. It is stable but not in-place: the merging step requires extra memory proportional to n, so its space complexity is O(n).
Sorting algorithms differ in the number of comparisons, the number of swaps, memory usage and stability. A stable sorting algorithm preserves the relative order of equal elements, which matters when records have multiple keys. Bubble sort, insertion sort and merge sort are stable; selection sort is not stable in its standard form.
| Algorithm | Best | Average | Worst | Space | Stable |
|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n^2) | O(n^2) | O(1) | Yes |
| Selection Sort | O(n^2) | O(n^2) | O(n^2) | O(1) | No |
| Insertion Sort | O(n) | O(n^2) | O(n^2) | O(1) | Yes |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Algorithm | Idea | Worst Time | Space |
|---|---|---|---|
| Bubble Sort | Swap adjacent out-of-order pairs | O(n^2) | O(1) |
| Selection Sort | Select minimum and place it | O(n^2) | O(1) |
| Insertion Sort | Insert each element in sorted part | O(n^2) | O(1) |
| Merge Sort | Divide, sort halves, merge | O(n log n) | O(n) |
| Pass | List after pass |
|---|---|
| Initial | [5, 1, 4, 2] |
| Pass 1 | [1, 4, 2, 5] |
| Pass 2 | [1, 2, 4, 5] |
| Pass 3 | [1, 2, 4, 5] |
range(n) instead of range(n - 1 - i) re-compares already placed elements and can cause IndexError.Sorting transforms unordered data into a structured form that can be searched, displayed and analysed efficiently. Bubble sort and selection sort are simple and in-place but slow, running in O(n^2) time; insertion sort shares that worst case but shines on small or nearly sorted data. Merge sort introduces the powerful divide-and-conquer strategy, guaranteeing O(n log n) time at the cost of O(n) extra space. Choosing among them requires balancing time, memory and stability for the specific problem. The next chapter on searching builds directly on this chapter: sorted data enables dramatically faster search techniques such as binary search.