Module 5: Sorting Algorithms

Sorting is not just about arranging elements.
It is about organizing data to enable faster searching, optimization, and decision-making.

In interviews, sorting problems test:

• Algorithmic thinking
• Trade-off understanding
• Time–space optimization
• Stability and memory awareness

Bubble Sort

Core Idea

Bubble sort repeatedly compares adjacent elements and swaps them if they are in the wrong order.
Larger elements “bubble up” to the end.

How It Works

• Compare arr[0] and arr[1]
• Swap if needed
• Continue till the largest element reaches the end
• Repeat for remaining elements

Example

for(int i = 0; i < n - 1; i++){
    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;
        }
    }
}

Analysis

• Best case (already sorted): O(n)
• Average & worst case: O(n²)
• Space: O(1)
• Stable: Yes

Used mainly for teaching, rarely in production.

Selection Sort

Core Idea

Find the smallest element and place it at the correct position.

How It Works

• Select minimum from unsorted part
• Swap with first unsorted index
• Reduce unsorted range

Example

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;
        }
    }
    int temp = arr[i];
    arr[i] = arr[minIndex];
    arr[minIndex] = temp;
}

Analysis

• Time: O(n²) in all cases
• Space: O(1)
• Stable: No (by default)

Good when memory writes are expensive.

Insertion Sort

Core Idea

Insert each element into its correct position in the sorted part.

How It Works

• First element is considered sorted
• Pick next element
• Shift larger elements
• Insert element

Example

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;
}

Analysis

• Best case: O(n)
• Worst case: O(n²)
• Space: O(1)
• Stable: Yes

Used in:

• Nearly sorted data
• Hybrid sorting algorithms

Merge Sort

Core Idea

Divide array into halves, sort each half, then merge.

Divide & Conquer Steps

• Divide array
• Sort recursively
• Merge sorted halves

Example

void mergeSort(int[] arr, int l, int r){
    if(l < r){
        int mid = l + (r - l) / 2;
        mergeSort(arr, l, mid);
        mergeSort(arr, mid + 1, r);
        merge(arr, l, mid, r);
    }
}

Analysis

• Time: O(n log n)
• Space: O(n)
• Stable: Yes

Used in:

• External sorting
• Linked lists
• Large datasets

Quick Sort

Core Idea

Choose a pivot, partition array, then sort subarrays.

Partition Logic

• Elements < pivot → left
• Elements > pivot → right

Example

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(arr, i, j);
        }
    }
    swap(arr, i + 1, high);
    return i + 1;
}

Analysis

• Best & average: O(n log n)
• Worst case: O(n²)
• Space: O(log n)
• Stable: No

Fastest in practice due to cache friendliness.

Heap Sort

Core Idea

Uses a binary heap to sort elements.

Steps

• Build max heap
• Swap root with last element
• Heapify reduced heap

Example

void heapSort(int[] arr){
    buildHeap(arr);
    for(int i = n - 1; i > 0; i--){
        swap(arr, 0, i);
        heapify(arr, 0, i);
    }
}

Analysis

• Time: O(n log n)
• Space: O(1)
• Stable: No

Used when worst-case guarantees are required.

---

Counting Sort

Core Idea

Count frequency of each element.

Example

int[] count = new int[max + 1];
for(int x : arr){
    count[x]++;
}

Analysis

• Time: O(n + k)
• Space: O(k)
• Stable: Yes

Used when:

• Data range is small
• Integers only

---

Radix Sort

Core Idea

Sort numbers digit by digit.

Steps

• Sort by least significant digit
• Move to most significant digit

Uses stable counting sort internally.

Analysis

• Time: O(d × (n + k))
• Space: O(n + k)
• Stable: Yes

Used in:

• Large integers
• Fixed-length keys

---

Bucket Sort

Core Idea

Distribute elements into buckets, sort each bucket.

Analysis

• Average: O(n)
• Worst: O(n²)
• Space: O(n)
• Stable: Depends on inner sort

Used for:

• Uniformly distributed data
• Floating-point values

---

Stability in Sorting

A sorting algorithm is stable if equal elements retain their relative order.

Example:

(3,A) (3,B) → after sort → (3,A) (3,B)

Important when sorting objects by multiple keys.

---

In-Place vs Out-of-Place Sorting

In-place:

• Uses constant extra memory
• Examples: Quick sort, Heap sort

Out-of-place:

• Uses extra memory
• Examples: Merge sort, Counting sort

---

Sorting Complexity Analysis

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