1. Merge Sort

Algorithm Overview

Merge Sort is a divide-and-conquer algorithm that recursively divides the array into halves, sorts them, and then merges them back together.

Time & Space Complexity

How It Works

Step 1 → Divide array into two halves
Step 2 → Recursively sort both halves
Step 3 → Merge the sorted halves

Key Functions

1. Merge Function

void merge(int arr[], int s, int e, int mid) {
    // Create temporary arrays for left and right parts
    int leftLength = mid - s + 1;
    int rightLength = e - mid;

    int *leftArr = new int[leftLength];
    int *rightArr = new int[rightLength];

    // Copy data to temp arrays
    int index = s;
    for(int i = 0; i < leftLength; i++) {
        leftArr[i] = arr[index++];
    }

    index = mid + 1;
    for(int i = 0; i < rightLength; i++) {
        rightArr[i] = arr[index++];
    }

    // Merge the temp arrays back
    int i = 0, j = 0, mainArrayIndex = s;

    while(i < leftLength && j < rightLength) {
        if(leftArr[i] < rightArr[j]) {
            arr[mainArrayIndex++] = leftArr[i++];
        } else {
            arr[mainArrayIndex++] = rightArr[j++];
        }
    }

    // Copy remaining elements
    while(i < leftLength) arr[mainArrayIndex++] = leftArr[i++];
    while(j < rightLength) arr[mainArrayIndex++] = rightArr[j++];

    delete[] leftArr;
    delete[] rightArr;
}

2. MergeSort Function

void mergeSort(int arr[], int s, int e) {
    if(s >= e) return; // Base case

    int mid = (s + e) / 2;
    mergeSort(arr, s, mid);        // Sort left half
    mergeSort(arr, mid + 1, e);    // Sort right half
    merge(arr, s, e, mid);         // Merge both halves
}

Visual Process

[10,80,110,90,50,30,40,20]
       ↓ (divide)
[10,80,110,90] [50,30,40,20]
       ↓           ↓
[10,80][110,90] [50,30][40,20]
   ↓      ↓       ↓      ↓
[10][80][110][90][50][30][40][20]
       ↓ (merge back up)
[10,20,30,40,50,80,90,110]

2. Quick Sort

Algorithm Overview

Quick Sort uses divide-and-conquer with a pivot element. Elements smaller than pivot go left, larger go right.

Time & Space Complexity