Sorting

Bubble sort

📌 Key Idea: In every pass, the maximum element goes (bubble up) to its correct position at the end of the array.

void bubble(vector<int> &arr)
{
    int n = arr.size();
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n - 1; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                swap(arr[j], arr[j + 1]);
            }
        }
    }
}
 
/*
Optimizations:
 
1. Outer loop runs only till n-1
   * After (n-1) passes, the array is guaranteed to be sorted.
 
2. Inner loop runs till (n-1-i)
   * After every pass, the largest element moves to its correct position.
   * Therefore, the last i elements are already sorted and can be skipped.
 
3. Early termination
   * If no swap occurs during a pass, the array is already sorted.
   * Stop further processing using a flag.
*/
void bubbleOptimized(vector<int> &arr)
{
    int n = arr.size();
 
    for (int i = 0; i < n - 1; i++)
    {
        bool isSorted = true;
 
        for (int j = 0; j < n - 1 - i; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                swap(arr[j], arr[j + 1]);
                isSorted = false;
            }
        }
 
        if (isSorted)
            break;
    }
}

Case	Time Complexity
Best Case (already sorted) `isSorted = true`	`O(n)`
Worst Case	`O(n²)`

Selection Sort

📌 Key Idea: In every pass, find the smallest element correct position in the sorted postion at front

void selectionsort (int a[], int n) {
    for (int i = 0; i < n - 1 ; i++) {
        //step 1 --> temperory set
        int imin = i; // ith position
 
        //step 2 --> finding imin
        for (int j = i + 1 ; j < n ; j++) {
            if (a[j] < a[imin])
            {
                imin = j;
            }
        }
 
        //step 3 --> swaping
        swap(a[i], a[imin]);
    }
}

Insertion Sort

📌 Key Idea: Build the sorted portion one element at a time by inserting the current element into its correct position among the already sorted elements.

void insertionSort(vector<int>& arr) {
    int n = arr.size();
 
    // [Sorted Array] [Curr Element] [Unsorted Array]
 
    // Outer loop -> pick elements one by one
    for (int i = 1; i < n; i++) {
 
        // Inner loop -> move current element to correct position in sorted Array    
        for (int j = i; j > 0; j--) {
 
            // Swap if left element is bigger
            if (arr[j] < arr[j - 1]) {
                swap(arr[j], arr[j - 1]);
            }
            else {
                break; // already sorted
            }
        }
    }
}
 
[5, 3, 4, 1]
 
Pass 1:
[3, 5, 4, 1]
 
Pass 2:
[3, 4, 5, 1]
 
Pass 3:
[1, 3, 4, 5]

Case	Time Complexity
Best Case (already sorted)	`O(n)`
Worst Case (reverse sorted)	`O(n²)`

Stability of Sorting Algorithms

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

Example:

[(5,A), (3,X), (5,B)]

[(3,X), (5,A), (5,B)] # Stable sorted

A remains before B, so the sort is stable.

Note

Stable ✅ = Bubble, Insersion, Merge Not Stable ❌ = selection, quick, HeapSort

Merge Sort

📌 Key Idea: Divide the array into two halves, recursively sort both halves, then merge the sorted halves.

void merge(vector<int>& nums, int l, int mid, int r)
{
    vector<int> sorted;
 
    int l1 = l;
    int r1 = mid;
 
    int l2 = mid + 1;
    int r2 = r;
 
    while (l1 <= r1 && l2 <= r2)
    {
        if (nums[l1] <= nums[l2])
            sorted.push_back(nums[l1++]);
        else
            sorted.push_back(nums[l2++]);
    }
 
    while (l1 <= r1)
        sorted.push_back(nums[l1++]);
 
    while (l2 <= r2)
        sorted.push_back(nums[l2++]);
 
    for (auto &ele : sorted)
        nums[l++] = ele;
}
 
void mergeSort(vector<int>& nums, int l, int r)
{
    if (l >= r)
        return;
 
    int mid = l + (r - l) / 2;
 
    mergeSort(nums, l, mid);      // Left Half
    mergeSort(nums, mid + 1, r);  // Right Half
 
    merge(nums, l, mid, r);
}

Time Complexity

Component	Time
Merge Sorted Array Fun	`O(n)`
Recursion Stack	`O(log n)` as getting split in half recursively

Space Complexity

Component	Space
Temporary Array in Merge Fun	`O(n)`
Recursion Stack	`O(log n)`

Questions

Count Inversions (GFG) Find All nums[i] > nums[j] for i<j

// GFG - Count Inversions
 
class Solution {
public:
    int InvCount = 0;
 
    void countInversion(vector<int> &nums, int l1, int r1, int l2, int r2) {
        while (l1 <= r1 && l2 <= r2) {
            if (nums[l1] > nums[l2]) {
                InvCount += (r1 - l1 + 1);
                l2++;
            } else {
                l1++;
            }
        }
    }
 
    void merge(vector<int>& nums, int l, int mid, int r) {
        vector<int> sorted;
 
        int l1 = l, r1 = mid;
        int l2 = mid + 1, r2 = r;
 
        countInversion(nums, l1, r1, l2, r2);
 
        while (l1 <= r1 && l2 <= r2) {
            nums[l1] <= nums[l2]
                ? sorted.push_back(nums[l1++])
                : sorted.push_back(nums[l2++]);
        }
 
        while (l1 <= r1)
            sorted.push_back(nums[l1++]);
 
        while (l2 <= r2)
            sorted.push_back(nums[l2++]);
 
        for (auto &ele : sorted)
            nums[l++] = ele;
    }
 
    void mergeSort(vector<int>& nums, int l, int r) {
        if (l >= r)
            return;
 
        int mid = l + (r - l) / 2;
 
        mergeSort(nums, l, mid);
        mergeSort(nums, mid + 1, r);
 
        merge(nums, l, mid, r);
    }
 
    int inversionCount(vector<int>& nums) {
        mergeSort(nums, 0, nums.size() - 1);
        return InvCount;
    }
};

Reverse Pairs (LeetCode 493) Find All nums[i] > 2 * nums[j] for i<j`

// LeetCode 493 - Reverse Pairs
 
class Solution {
public:
    int InvCount = 0;
 
    void countInversion(vector<int> &nums, int l1, int r1, int l2, int r2) {
        while (l1 <= r1 && l2 <= r2) {
            if ((long long)nums[l1] > 2 * (long long)nums[l2]) {
                InvCount += (r1 - l1 + 1);
                l2++;
            } else {
                l1++;
            }
        }
    }
 
    void merge(vector<int>& nums, int l, int mid, int r) {
        vector<int> sorted;
 
        int l1 = l, r1 = mid;
        int l2 = mid + 1, r2 = r;
 
        countInversion(nums, l1, r1, l2, r2);
 
        while (l1 <= r1 && l2 <= r2) {
            nums[l1] <= nums[l2]
                ? sorted.push_back(nums[l1++])
                : sorted.push_back(nums[l2++]); // we can remove countInversion & add  InvCount+=(r1-l1+1) here for optimization to avoid extra n loop
        }
 
        while (l1 <= r1)
            sorted.push_back(nums[l1++]);
 
        while (l2 <= r2)
            sorted.push_back(nums[l2++]);
 
        for (auto &ele : sorted)
            nums[l++] = ele;
    }
 
    void mergeSort(vector<int>& nums, int l, int r) {
        if (l >= r)
            return;
 
        int mid = l + (r - l) / 2;
 
        mergeSort(nums, l, mid);
        mergeSort(nums, mid + 1, r);
 
        merge(nums, l, mid, r);
    }
 
    int reversePairs(vector<int>& nums) {
        mergeSort(nums, 0, nums.size() - 1);
        return InvCount;
    }
};

Quick Sort

📌 Key Idea: Pick a pivot element, place it in its correct sorted position, then recursively sort the left and right partitions.

int partition(vector<int>& nums, int l, int r)
{
    int pivot = nums[r];
    int pIndex = l;
 
    for (int i = l; i < r; i++)
    {
        if (nums[i] < pivot)
        {
            swap(nums[pIndex], nums[i]);
            pIndex++;
        }
    }
 
    swap(nums[pIndex], nums[r]);
 
    return pIndex;
}
 
void quickSort(vector<int>& nums, int l, int r)
{
    if (l >= r)
        return;
 
    int p = partition(nums, l, r);
 
    quickSort(nums, l, p - 1);
    quickSort(nums, p + 1, r);
}

nums = [4, 2, 8, 1, 7, 3]
 
Pivot = 3
 
After partition:
 
[2, 1] | 3 | [8, 7, 4]
 
Pivot Index = 2

Time Complexity

Case	Time Complexity
Best Case	`O(n log n)`
Worst Case	`O(n²)`
Space Complexity

Component	Space
Recursion Stack (Average)	`O(log n)`
Recursion Stack (Worst)	`O(n)`

📌 Interview Tip:

Algorithm	Average	Worst	Space
Merge Sort	`O(n log n)`	`O(n log n)`	`O(n)`
Quick Sort	`O(n log n)`	`O(n²)`	`O(log n)`

Comparison of Basic Sorting Algorithms

Property	Bubble Sort	Selection Sort	Insertion Sort	Merge Sort	Quick Sort
Best Time	`O(n)`	`O(n²)`	`O(n)`	`O(n log n)`	`O(n log n)`
Average Time	`O(n²)`	`O(n²)`	`O(n²)`	`O(n log n)`	`O(n log n)`
Worst Time	`O(n²)`	`O(n²)`	`O(n²)`	`O(n log n)`	`O(n²)`
Space Complexity	`O(1)`	`O(1)`	`O(1)`	`O(n)` + `O(log n)`	`O(log n)`
Stable	✅	❌	✅	✅	❌
In-Place	✅	✅	✅	❌	✅
Best For	Small / Nearly Sorted	Minimizing Swaps	Nearly Sorted Arrays	Guaranteed Performance	Fast Practical Sorting

In-Place:- It modifies the original array directly instead of creating another array.

If Asked…	Choose
Small, nearly sorted array	Insertion Sort
Need stable sorting	Merge Sort / Insertion Sort
Need guaranteed `O(n log n)`	Merge Sort
Need in-place `O(n log n)` average	Quick Sort
Minimum swaps required	Selection Sort
Best practical performance	Quick Sort
Linked List Sorting	Merge Sort
External Sorting (Huge Files)	Merge Sort

C++ STL std::sort() uses Introsort, a hybrid of Quick Sort + Heap Sort + Insertion Sort. It provides O(n log n) worst-case time complexity while maintaining excellent practical performance.

Om's Brain

Explorer

Bubble sort

Selection Sort

Insertion Sort

Stability of Sorting Algorithms

Merge Sort

Questions

Quick Sort

Table of Contents

Mindmap

Graph View