Chapter 4: Sorting Algorithms

Introduction

Sorting is the process of arranging elements in a specific order (ascending or descending). It's one of the most studied problems in computer science because sorted data enables efficient searching, data analysis, and optimization. Understanding sorting algorithms teaches fundamental algorithmic techniques like divide-and-conquer, recursion, and complexity trade-offs.

Why This Matters

Sorting appears everywhere:

Databases organizing query results
E-commerce sites showing products by price
File systems displaying files by name/date
Search engines ranking results
Operating systems scheduling processes

Different sorting algorithms have different characteristics:

Performance: O(n²) vs O(n log n) matters for large datasets
Stability: Preserving relative order of equal elements
Memory: In-place vs requiring extra space
Adaptivity: Performance on partially sorted data

How to Study This Chapter

Visualize each algorithm - Draw array transformations step by step
Implement from scratch - Don't just copy; understand why it works
Compare performance - Time algorithms with different input sizes
Understand trade-offs - Speed vs memory vs stability
Practice variations - Solve problems requiring sorting knowledge

Sorting Algorithm Categories

Simple Sorts - O(n²)

Bubble Sort
Selection Sort
Insertion Sort

Efficient Sorts - O(n log n)

Merge Sort
Quick Sort
Heap Sort

Special Purpose

Counting Sort - O(n + k)
Radix Sort - O(d × n)
Bucket Sort - O(n + k)

Bubble Sort

Bubble sort repeatedly steps through the list, compares adjacent elements, and swaps them if they're in the wrong order.

Algorithm

1. For i from 0 to n-1:
   a. For j from 0 to n-i-1:
      - If arr[j] > arr[j+1], swap them
   b. After each pass, largest element "bubbles" to the end

Visualization

Initial: [64, 34, 25, 12, 22, 11, 90]

Pass 1:
[34, 64, 25, 12, 22, 11, 90]  (64 > 34, swap)
[34, 25, 64, 12, 22, 11, 90]  (64 > 25, swap)
[34, 25, 12, 64, 22, 11, 90]  (64 > 12, swap)
[34, 25, 12, 22, 64, 11, 90]  (64 > 22, swap)
[34, 25, 12, 22, 11, 64, 90]  (64 > 11, swap)
                        ^^^ 90 in final position

Pass 2:
[25, 34, 12, 22, 11, 64, 90]
...
                    ^^^ 64 in final position

C Implementation

#include <stdio.h>

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // Swap
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = 7;

    printf("Original: ");
    printArray(arr, n);

    bubbleSort(arr, n);

    printf("Sorted: ");
    printArray(arr, n);

    return 0;
}

C++ Implementation

#include <iostream>
#include <vector>
using namespace std;

void bubbleSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
            }
        }
    }
}

int main() {
    vector<int> arr = {64, 34, 25, 12, 22, 11, 90};

    bubbleSort(arr);

    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

Java Implementation

import java.util.Arrays;

public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    // Swap
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        bubbleSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

Optimized Bubble Sort

Add a flag to detect if array is already sorted:

void bubbleSortOptimized(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int swapped = 0;

        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = 1;
            }
        }

        // If no swaps, array is sorted
        if (!swapped) break;
    }
}

Complexity Analysis

Time Complexity:
- Best case: O(n) - already sorted (with optimization)
- Average case: O(n²)
- Worst case: O(n²) - reverse sorted
Space Complexity: O(1)
Stable: Yes - equal elements maintain relative order
In-place: Yes

Selection Sort

Selection sort finds the minimum element and places it at the beginning, then repeats for the remaining elements.

Algorithm

1. For i from 0 to n-1:
   a. Find minimum element in arr[i...n-1]
   b. Swap it with arr[i]

C Implementation

#include <stdio.h>

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;

        // Find minimum in remaining array
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }

        // Swap minimum with current position
        if (minIndex != i) {
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = 5;

    selectionSort(arr, n);

    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

C++ Implementation

#include <iostream>
#include <vector>
using namespace std;

void selectionSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;

        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }

        if (minIndex != i) {
            swap(arr[i], arr[minIndex]);
        }
    }
}

int main() {
    vector<int> arr = {64, 25, 12, 22, 11};
    selectionSort(arr);

    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

Java Implementation

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;

            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }

            if (minIndex != i) {
                int temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 25, 12, 22, 11};
        selectionSort(arr);

        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}

Complexity Analysis

Time Complexity: O(n²) for all cases - always does the same comparisons
Space Complexity: O(1)
Stable: No (can be made stable with modifications)
In-place: Yes
Good for: Small arrays or when swap cost is high

Insertion Sort

Insertion sort builds sorted array one element at a time by inserting each element into its correct position.

Algorithm

1. For i from 1 to n-1:
   a. key = arr[i]
   b. j = i - 1
   c. Shift elements greater than key to the right
   d. Insert key at correct position

Visualization

[12, 11, 13, 5, 6]

i=1: key=11
[12, 12, 13, 5, 6]  (shift 12)
[11, 12, 13, 5, 6]  (insert 11)

i=2: key=13
[11, 12, 13, 5, 6]  (already in place)

i=3: key=5
[11, 12, 13, 13, 6] (shift 13)
[11, 12, 12, 13, 6] (shift 12)
[11, 11, 12, 13, 6] (shift 11)
[5, 11, 12, 13, 6]  (insert 5)

i=4: key=6
[5, 11, 12, 13, 13] (shift 13)
[5, 11, 12, 12, 13] (shift 12)
[5, 11, 11, 12, 13] (shift 11)
[5, 6, 11, 12, 13]  (insert 6)

C Implementation

#include <stdio.h>

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;

        // Shift elements greater than key to the right
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }

        arr[j + 1] = key;
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = 5;

    insertionSort(arr, n);

    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

C++ Implementation

#include <iostream>
#include <vector>
using namespace std;

void insertionSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;

        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }

        arr[j + 1] = key;
    }
}

int main() {
    vector<int> arr = {12, 11, 13, 5, 6};
    insertionSort(arr);

    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

Java Implementation

public class InsertionSort {
    public static void insertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;

            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }

            arr[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6};
        insertionSort(arr);

        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}

Complexity Analysis

Time Complexity:
- Best case: O(n) - already sorted
- Average case: O(n²)
- Worst case: O(n²) - reverse sorted
Space Complexity: O(1)
Stable: Yes
In-place: Yes
Adaptive: Works well on partially sorted data
Good for: Small arrays, nearly sorted data, online sorting

Merge Sort

Merge sort uses divide-and-conquer: divide array in half, recursively sort halves, merge sorted halves.

Algorithm

1. If array has 1 element, return (base case)
2. Divide array into two halves
3. Recursively sort left half
4. Recursively sort right half
5. Merge the two sorted halves

Visualization

[38, 27, 43, 3, 9, 82, 10]

Divide:
[38, 27, 43, 3] | [9, 82, 10]
[38, 27] [43, 3] | [9, 82] [10]
[38] [27] [43] [3] | [9, 82] [10]
[38] [27] [43] [3] | [9] [82] [10]

Merge:
[27, 38] [3, 43] | [9, 82] [10]
[3, 27, 38, 43] | [9, 10, 82]
[3, 9, 10, 27, 38, 43, 82]

C Implementation

#include <stdio.h>
#include <stdlib.h>

void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    // Create temp arrays
    int *L = (int*)malloc(n1 * sizeof(int));
    int *R = (int*)malloc(n2 * sizeof(int));

    // Copy data
    for (int i = 0; i < n1; i++) {
        L[i] = arr[left + i];
    }
    for (int j = 0; j < n2; j++) {
        R[j] = arr[mid + 1 + j];
    }

    // Merge back
    int i = 0, j = 0, k = left;

    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    // Copy remaining
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }

    free(L);
    free(R);
}

void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;

        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

        merge(arr, left, mid, right);
    }
}

int main() {
    int arr[] = {38, 27, 43, 3, 9, 82, 10};
    int n = 7;

    mergeSort(arr, 0, n - 1);

    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

C++ Implementation

#include <iostream>
#include <vector>
using namespace std;

void merge(vector<int>& arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    vector<int> L(n1), R(n2);

    for (int i = 0; i < n1; i++) {
        L[i] = arr[left + i];
    }
    for (int j = 0; j < n2; j++) {
        R[j] = arr[mid + 1 + j];
    }

    int i = 0, j = 0, k = left;

    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k++] = L[i++];
        } else {
            arr[k++] = R[j++];
        }
    }

    while (i < n1) {
        arr[k++] = L[i++];
    }

    while (j < n2) {
        arr[k++] = R[j++];
    }
}

void mergeSort(vector<int>& arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;

        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

        merge(arr, left, mid, right);
    }
}

int main() {
    vector<int> arr = {38, 27, 43, 3, 9, 82, 10};

    mergeSort(arr, 0, arr.size() - 1);

    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

Java Implementation

public class MergeSort {
    public static void merge(int[] arr, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;

        int[] L = new int[n1];
        int[] R = new int[n2];

        for (int i = 0; i < n1; i++) {
            L[i] = arr[left + i];
        }
        for (int j = 0; j < n2; j++) {
            R[j] = arr[mid + 1 + j];
        }

        int i = 0, j = 0, k = left;

        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k++] = L[i++];
            } else {
                arr[k++] = R[j++];
            }
        }

        while (i < n1) {
            arr[k++] = L[i++];
        }

        while (j < n2) {
            arr[k++] = R[j++];
        }
    }

    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2;

            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);

            merge(arr, left, mid, right);
        }
    }

    public static void main(String[] args) {
        int[] arr = {38, 27, 43, 3, 9, 82, 10};
        mergeSort(arr, 0, arr.length - 1);

        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}

Complexity Analysis

Time Complexity: O(n log n) for all cases
Space Complexity: O(n) - requires temporary arrays
Stable: Yes
Not in-place: Requires extra memory
Good for: Large datasets, linked lists, external sorting

Quick Sort

Quick sort picks a pivot, partitions array so elements < pivot are left, > pivot are right, then recursively sorts partitions.

Algorithm

1. Choose pivot (often last element)
2. Partition: rearrange so elements < pivot are left, > pivot are right
3. Recursively quicksort left partition
4. Recursively quicksort right partition

C Implementation

#include <stdio.h>

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;

    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            // Swap
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    // Place pivot in correct position
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;

    return i + 1;
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);

        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = 6;

    quickSort(arr, 0, n - 1);

    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

C++ Implementation

#include <iostream>
#include <vector>
using namespace std;

int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;

    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }

    swap(arr[i + 1], arr[high]);
    return i + 1;
}

void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);

        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int main() {
    vector<int> arr = {10, 7, 8, 9, 1, 5};

    quickSort(arr, 0, arr.size() - 1);

    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

Java Implementation

public class QuickSort {
    public static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = low - 1;

        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;

        return i + 1;
    }

    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);

            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }

    public static void main(String[] args) {
        int[] arr = {10, 7, 8, 9, 1, 5};
        quickSort(arr, 0, arr.length - 1);

        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}

Complexity Analysis

Time Complexity:
- Best/Average: O(n log n)
- Worst case: O(n²) - already sorted with bad pivot choice
Space Complexity: O(log n) - recursion stack
Stable: No
In-place: Yes
Good for: Large datasets, often fastest in practice

Optimizations

Random Pivot: Choose random pivot to avoid worst case

int randomPivot = low + rand() % (high - low + 1);
swap(&arr[randomPivot], &arr[high]);

Comparison of Sorting Algorithms

Algorithm	Best	Average	Worst	Space	Stable	In-place
Bubble	O(n)	O(n²)	O(n²)	O(1)	Yes	Yes
Selection	O(n²)	O(n²)	O(n²)	O(1)	No	Yes
Insertion	O(n)	O(n²)	O(n²)	O(1)	Yes	Yes
Merge	O(n log n)	O(n log n)	O(n log n)	O(n)	Yes	No
Quick	O(n log n)	O(n log n)	O(n²)	O(log n)	No	Yes

Common Mistakes

Off-by-one errors - Wrong loop bounds
Not handling empty/single element - Missing base cases
Integer overflow in merge - Calculating mid incorrectly
Inefficient pivot choice - Always choosing first/last in quicksort
Memory leaks in C - Not freeing temporary arrays
Modifying during comparison - Unstable sorts
Wrong partition logic - Infinite recursion in quicksort

Debugging Tips

Print array after each pass - Visualize sorting progress
Test edge cases - Empty, single element, duplicates, sorted, reverse
Verify stability - Track equal elements
Check recursion depth - Prevent stack overflow
Use assertions - Verify partitioning correctness
Test with small inputs first - Easy to trace manually
Use debugger - Step through recursive calls

Mini Exercises

Implement bubble sort with early termination
Sort array of strings using insertion sort
Count inversions using merge sort
Implement 3-way quicksort for duplicates
Find kth largest element using quickselect
Sort linked list using merge sort
Implement in-place merge sort
Sort array with only 0s, 1s, and 2s (Dutch flag)
Implement cocktail shaker sort
Compare sorting algorithm performance experimentally

Review Questions

Why is merge sort stable but quicksort is not?
When would you choose insertion sort over quicksort?
How does pivot selection affect quicksort performance?
Why does merge sort require O(n) extra space?
What makes an algorithm adaptive?

Reference Checklist

By the end of this chapter, you should be able to:

Implement bubble, selection, insertion sort
Implement merge sort and quick sort
Analyze time and space complexity
Understand stability and in-place sorting
Choose appropriate algorithm for the problem
Recognize worst-case scenarios
Optimize sorting algorithms
Debug sorting implementations

Next Steps

Now that you understand sorting algorithms, Chapter 5 explores linked lists—a dynamic data structure that excels where arrays struggle. You'll learn singly linked lists, doubly linked lists, and circular lists with their operations and applications.

Key Takeaway: Different sorting algorithms have different trade-offs. Simple sorts (O(n²)) work well for small or nearly sorted data. Efficient sorts (O(n log n)) scale to large datasets. Understanding these trade-offs helps you choose the right algorithm for your specific needs.