Sorting Algorithms

Elementary Sorting Algorithms

Sorting algorithms arrange the elements of a list in a specific order (ascending or descending). We will begin with three elementary sorting algorithms: bubble sort, selection sort, and insertion sort.

Bubble Sort

Algorithm

Bubble sort works by repeatedly stepping through the list, comparing adjacent elements and swapping them if they are in the wrong order. This process is repeated until the list is sorted. Larger elements “bubble” to the end of the list.

Python Implementation

def bubble_sort(data):
    n = len(data)
    for i in range(n):
        # Last i elements are already in place
        for j in range(0, n - i - 1):
            if data[j] > data[j + 1]:
                data[j], data[j + 1] = data[j + 1], data[j]  # Swap

Time Complexity

• Worst-case: $O(n^2)$ - When the list is in reverse order.
• Best-case: $O(n)$ - When the list is already sorted. A check can be added to stop if no swaps are performed in a pass.
• Average-case: $O(n^2)$ - On average, we expect a quadratic number of comparisons and swaps.

Correctness Proof (Loop Invariant)

Invariant: At the start of each iteration of the outer loop (indexed by i), the last i elements of the list (data[n-i...n-1]) are sorted and contain the i largest elements of the original list.

• Initialization: Before the outer loop starts (i=0), the last 0 elements are trivially sorted, and there are no “largest elements” placed yet. So, the invariant holds.
• Maintenance: Suppose the invariant holds at the beginning of the outer loop iteration i. In the inner loop (indexed by j), adjacent elements are compared, and swapped if they are in the wrong order. After the i-th iteration of outer loop, the (n-i)th largest element will be bubbled up to data[n-i-1]. Therefore, data[n-i-1...n-1] will contain the i+1 largest elements, sorted. This ensures that the invariant holds for the next iteration (i+1).
• Termination: The outer loop terminates when i = n. At this point, the invariant states that the last n elements (which is the entire list) are sorted and contain the n largest elements (which is all of them). Hence, the entire list is sorted.

Selection Sort

Algorithm

Selection sort divides the list into two parts: sorted and unsorted. It repeatedly selects the smallest (or largest) element from the unsorted part and moves it to the end of the sorted part.

Python Implementation

def selection_sort(data):
    n = len(data)
    for i in range(n):
        min_index = i
        for j in range(i + 1, n):
            if data[j] < data[min_index]:
                min_index = j
        data[i], data[min_index] = data[min_index], data[i]  # Swap

Time Complexity

• Worst-case: $O(n^2)$ - In each iteration, we scan the remaining unsorted part to find the minimum element.
• Best-case: $O(n^2)$ - The number of comparisons is always the same, irrespective of the initial order.
• Average-case: $O(n^2)$ - Similar to the worst case.

Correctness Proof (Loop Invariant)

Invariant: At the start of each iteration of the outer loop (indexed by i), the first i elements of the list (data[0...i-1]) are sorted and contain the i smallest elements of the original list, and all elements in data[i...n-1] are greater than or equal to the elements in data[0...i-1].

• Initialization: Before the outer loop starts (i=0), the first 0 elements are trivially sorted and smallest, and there are no constraints on data[0...n-1]. So, the invariant holds.
• Maintenance: Suppose the invariant holds at the beginning of iteration i. The inner loop (indexed by j) finds the index min_index of the smallest element in data[i...n-1]. We then swap data[i] with data[min_index]. Now, data[0...i] contains the i+1 smallest elements, sorted, and all elements in data[i+1...n-1] are greater than or equal to those in data[0...i]. Thus the invariant holds for the next iteration.
• Termination: The outer loop terminates when i = n. The invariant then states that the first n elements (entire list) are sorted and contains the n smallest elements (all elements), thus the entire list is sorted.

Insertion Sort

Algorithm

Insertion sort also divides the list into sorted and unsorted parts. It iterates through the unsorted part and inserts each element into its correct position in the sorted part by shifting greater elements to the right.

Python Implementation

def insertion_sort(data):
    for i in range(1, len(data)):
        key = data[i]
        j = i - 1
        while j >= 0 and key < data[j]:
            data[j + 1] = data[j]
            j -= 1
        data[j + 1] = key

Time Complexity

• Worst-case: $O(n^2)$ - When the list is in reverse order, each element has to be shifted to the beginning.
• Best-case: $O(n)$ - When the list is already sorted, each element is compared only once.
• Average-case: $O(n^2)$ - On average, we expect to shift half of the sorted part for each element.

Correctness Proof (Loop Invariant)

Invariant: At the start of each iteration of the outer loop (indexed by i), the sublist data[0...i-1] is sorted.

• Initialization: Before the outer loop starts (i=1), data[0...0] is a sublist of size 1, which is trivially sorted. So the invariant holds.
• Maintenance: Suppose the invariant holds at the beginning of iteration i. We pick key = data[i] and want to insert it into its correct sorted position within data[0...i-1]. The inner while loop shifts elements in data[0...i-1] that are greater than key one position to the right, creating a space for key. When the while loop terminates, we have found the position j+1 such that either j becomes -1 (meaning key is the smallest element seen so far and must be at index 0), or that data[j] is less than or equal to key. Thus, inserting key at position j+1 ensures that data[0...i] is sorted. Hence, the invariant holds for the next iteration.
• Termination: The outer loop terminates when i = n. At this point, the invariant states that data[0...n-1] (which is the entire list) is sorted. Thus the entire list has been sorted.

Advanced Sorting Algorithms

We now move on to more advanced sorting algorithms that offer better time complexity, especially for larger datasets: merge sort, quicksort, and heapsort.

Merge Sort

Algorithm

Merge sort is a divide-and-conquer algorithm. It works by recursively dividing the list into two halves until each sublist contains only one element (which is considered sorted). Then, it repeatedly merges the sorted sublists to produce new sorted sublists until there is only one sorted list remaining.

Python Implementation

def merge_sort(data):
    if len(data) > 1:
        mid = len(data) // 2
        left_half = data[:mid]
        right_half = data[mid:]
 
        merge_sort(left_half)
        merge_sort(right_half)
 
        i = j = k = 0
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                data[k] = left_half[i]
                i += 1
            else:
                data[k] = right_half[j]
                j += 1
            k += 1
 
        while i < len(left_half):
            data[k] = left_half[i]
            i += 1
            k += 1
 
        while j < len(right_half):
            data[k] = right_half[j]
            j += 1
            k += 1

Time Complexity

• Worst-case: $O(n\log n)$ - The list is divided logarithmically, and merging takes linear time.
• Best-case: $O(n\log n)$ - Same as the worst case, as the algorithm always divides and merges.
• Average-case: $O(n\log n)$ - On average, the performance is similar to the worst case.

Correctness Proof (Inductive Proof)

Base Case: If the length of the list is 0 or 1, it is already sorted. The algorithm does nothing, and thus the sorted list is returned (correctly).

Inductive Hypothesis: Assume that merge_sort correctly sorts all sublists of size less than n, for n>1.

Inductive Step: Consider a list of size n (n>1). The list is split into two sublists, left_half and right_half. Since both sublists have size less than n, by the inductive hypothesis, the calls merge_sort(left_half) and merge_sort(right_half) correctly sort these sublists.

Now, we need to show that merging the two sorted sublists results in a correctly sorted list. This is proven by loop invariant for merge process :

Invariant (for merge): At the start of each iteration of the merge while loop, the data[0...k-1] contains the smallest k elements from left_half and right_half in sorted order, and data[k...n-1] is unchanged. Also, i and j are the indices of the next elements to be considered from left_half and right_half, respectively.

• Initialization: Before the while loop starts, k=0, i=0, j=0 so data[0...k-1] is empty (trivially sorted), and i, j point to starts of respective arrays.
• Maintenance: In each iteration, we compare left_half[i] and right_half[j]. The smaller element is copied to data[k], and the respective index (i or j) and k are incremented. Since left_half and right_half are sorted, the element copied is the next smallest element overall. Thus data[0...k] is sorted and contains the k+1 smallest elements and the invariant is maintained.
• Termination: The loop terminates when either i reaches the end of left_half or j reaches the end of right_half. The remaining elements of the non-empty list are then copied into data (they are the next largest element as lists were sorted) ensuring the entire data is sorted.

Since the merge step is correct, and by the inductive hypothesis the sublists are correctly sorted, the list of size n is also correctly sorted. Therefore by induction, merge_sort correctly sorts any list.

Quicksort

Algorithm

Quicksort is another divide-and-conquer algorithm. It works by selecting a ‘pivot’ element from the list and partitioning the other elements into two sublists, according to whether they are less than or greater than the pivot. The sublists are then recursively sorted.

Python Implementation

import random
 
def quicksort(data):
    if len(data) < 2:
        return data
    else:
        pivot_index = random.randint(0, len(data)-1)  # Randomly choose pivot to avoid worst case
        pivot = data[pivot_index]
        less = [i for i in data if i < pivot]
        greater = [i for i in data if i > pivot]
        equal = [i for i in data if i == pivot]
        return quicksort(less) + equal + quicksort(greater)

Time Complexity

• Worst-case: $O(n^2)$ - When the pivot consistently divides the list very unevenly (e.g., one sublist has 0 elements and the other n-1 elements).
• Best-case: $O(n\log n)$ - When the pivot always divides the list into roughly equal sublists.
• Average-case: $O(n\log n)$ - On average, with random pivot selection, we expect a balanced partition.

Correctness Proof (Inductive Proof)

Base Case: If the list has size 0 or 1, it’s already sorted. The algorithm returns the list as is, which is correct.

Inductive Hypothesis: Assume that quicksort correctly sorts all sublists of size less than n, for n>1.

Inductive Step: Consider a list of size n (n>1). We pick a pivot and partition the list into three sublists: less (elements less than the pivot), equal (elements equal to the pivot), and greater (elements greater than the pivot). Each of these sublists has size less than n. By the inductive hypothesis, quicksort(less) and quicksort(greater) correctly sort these sublists. Since less contains elements smaller than pivot and greater contains elements larger than pivot, the concatenation quicksort(less) + equal + quicksort(greater) will result in a sorted list.

Therefore, by induction, quicksort correctly sorts any list.

Heapsort

Algorithm

Heapsort uses a binary heap data structure to sort a list. It first builds a max-heap from the list, where the largest element is at the root. Then, it repeatedly removes the largest element from the heap and adds it to the end of the sorted part of the list. After removing the largest element, it restores the heap property.

Python Implementation

def heapify(data, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2
 
    if left < n and data[left] > data[largest]:
        largest = left
 
    if right < n and data[right] > data[largest]:
        largest = right
 
    if largest != i:
        data[i], data[largest] = data[largest], data[i]  # Swap
        heapify(data, n, largest)
 
def heapsort(data):
    n = len(data)
 
    # Build max heap
    for i in range(n // 2 - 1, -1, -1):
        heapify(data, n, i)
 
    # Extract elements one by one
    for i in range(n - 1, 0, -1):
        data[i], data[0] = data[0], data[i]  # Swap
        heapify(data, i, 0)

Time Complexity

• Worst-case: $O(n\log n)$ - Building the heap takes O(n) time, and each of the n extractions takes O(log n) time.
• Best-case: $O(n\log n)$ - Same as the worst case.
• Average-case: $O(n\log n)$ - Similar to the worst case.

Correctness Proof (Loop Invariant)

Invariant (for heapify): At the start of each call to heapify(data, n, i), the binary trees rooted at the left and right children of node i are max-heaps, but the element at i might be smaller than its children.

• Initialization: When heapify is first called, the subtrees at the children are either leaves (trivially max-heaps), or have been previously heapified, satisfying the invariant.

• Maintenance: The function identifies the largest element among the node i and its children. If the largest is not i, it swaps i with the largest child and recursively calls heapify on that child’s subtree. This restores the max-heap property in that subtree and ensures that the invariant holds for the next recursive call.

• Termination: The recursion terminates when the node i is a leaf node, or the largest element is already at i, which implies we have a max heap rooted at the original index i. At that time a max heap property is restored at i and below (in the subtree).

Invariant (for building max-heap): At the start of each iteration of the first for loop (in heapsort), all nodes with index greater than i are roots of max-heaps.

• Initialization: Before the loop starts, for i from n//2 -1 to 0, consider the children of node i. Nodes greater than n//2 - 1 are leaves. Any node with only leaf as its children is trivially a max heap, so for i = n//2 -1 , children satisfy the invariant.

• Maintenance: In each iteration, heapify(data, n, i) is called. The invariant for heapify ensures that after calling this function, the subtree rooted at i becomes a max-heap. After this, all nodes with index greater than i-1 are roots of max heaps. Decrementing i ensures that the invariant holds for the next iteration.

• Termination: The loop terminates when i = -1. At this point, the invariant states that all nodes (entire array from 0 to n-1) are roots of max-heaps. Hence, data is now a max-heap.

Invariant (for sorting): At the start of each iteration of the second for loop (in heapsort), the sublist data[i+1...n-1] contains the i+1 largest elements in sorted order, and data[0...i] forms a max-heap containing the remaining elements.

• Initialization: Before the loop starts, the entire list data[0...n-1] is a max heap. data[n...n-1] is empty, trivially containing the 0 largest elements in sorted order. The remaining data[0...n-1] forms a max heap.

• Maintenance: In each iteration, the largest element (root of the max-heap) is swapped with the last element of the heap part (data[i]). Now the last i+1 elements contains i+1 largest elements, but the root may not maintain the max heap property. Then the heap size is reduced by 1 (by considering data[0...i-1]), and heapify(data, i, 0) is called to restore the max-heap property on the remaining elements data[0...i-1]. After this, data[i...n-1] contains n-i largest elements in sorted order and data[0...i-1] is a max heap. The invariant thus holds for the next iteration.

• Termination: The loop terminates when i = 0. At this point, the invariant states that data[1...n-1] contains the n-1 largest elements in sorted order, and data[0] contains the smallest element. Therefore, the entire list data[0...n-1] is sorted.