Divide and Conquer VTU BCSL40A

Merge Sort

Merge Sort is a stable divide-and-conquer sorting algorithm that recursively divides the array in half, sorts each half, and merges them back in order.

Time Complexity

O(n log n)

Space Complexity

O(n)

Paradigm

Divide and Conquer

Introduction

Merge Sort is a classic divide-and-conquer sorting algorithm invented by John von Neumann in 1945. It works by recursively dividing the array into two halves, sorting each half, and merging them back in sorted order. Merge Sort guarantees O(n log n) performance in all cases, making it more reliable than Quick Sort for worst-case scenarios. It is also stable.

Problem Statement

Sort an array of n elements using Merge Sort and demonstrate O(n log n) time complexity by measuring execution time for random arrays of sizes 5000, 10000, 15000, and 20000.

Real World Applications

→ External sorting (sorting data that doesn't fit in memory)
→ Sorting linked lists efficiently
→ Counting inversions in an array
→ Used in merge of sorted database tables
→ Java's Arrays.sort() for objects uses Merge Sort variant

Algorithm Explanation

Sort(arr, low, high) computes mid = (low+high)/2, then recursively sorts arr[low..mid] and arr[mid+1..high], then calls Merge to combine them. Merge(arr, low, mid, high) uses a temporary array: compare elements from both halves and place smaller one in result. This ensures the merged result is sorted.

Step-by-Step Procedure

1 If low >= high, return (base case — single element is sorted).
2 Compute mid = (low + high) / 2.
3 Recursively sort left half: sort(arr, low, mid).
4 Recursively sort right half: sort(arr, mid+1, high).
5 Merge both halves: compare arr[i] and arr[j], place smaller in res[], advance that pointer.
6 Copy remaining elements from either half into res[].
7 Copy res[] back into arr[low..high].

Complete C Program

Merge.c

View on GitHub ↗

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

void Merge(int arr[], int low, int mid, int high) {
    int i = low, j = mid + 1, k = low;
    int res[high + 1];
    while(i <= mid && j <= high) {
        if(arr[i] < arr[j])
            res[k++] = arr[i++];
        else
            res[k++] = arr[j++];
    }
    while(i <= mid) res[k++] = arr[i++];
    while(j <= high) res[k++] = arr[j++];
    for(int m = low; m <= high; m++)
        arr[m] = res[m];
}

void sort(int arr[], int low, int high) {
    if(low < high) {
        int mid = (low + high) / 2;
        sort(arr, low, mid);
        sort(arr, mid + 1, high);
        Merge(arr, low, mid, high);
    }
}

void generateRandomArray(int arr[], int n) {
    srand(time(NULL));
    for(int i = 0; i < n; i++) arr[i] = rand();
}

int main() {
    int num_values[] = {5000, 10000, 15000, 20000};
    for(int i = 0; i < 4; i++) {
        int n = num_values[i];
        int *arr = (int *)malloc(n * sizeof(int));
        generateRandomArray(arr, n);
        clock_t start = clock();
        sort(arr, 0, n - 1);
        clock_t end = clock();
        printf("%d\t%f\n", n, (double)(end - start) / CLOCKS_PER_SEC);
        free(arr);
    }
    return 0;
}

Sample Input & Output

Sample Input

(No input — generates random arrays automatically)

Expected Output

5000    0.002100
10000   0.004500
15000   0.007200
20000   0.009800

Dry Run / Trace

Array: [38, 27, 43, 3, 9, 82, 10]
Divide: [38,27,43,3] and [9,82,10]
Divide left: [38,27] and [43,3]
Merge [38] and [27] → [27,38]
Merge [43] and [3] → [3,43]
Merge [27,38] and [3,43] → [3,27,38,43]
Divide right: [9,82] and [10]
Merge [9] and [82] → [9,82]
Merge [9,82] and [10] → [9,10,82]
Final merge: [3,9,10,27,38,43,82]

Advantages & Disadvantages

✓ Advantages

+ Guaranteed O(n log n) in all cases (best, average, worst)
+ Stable sorting algorithm
+ Efficient for linked lists
+ Parallelizable — left and right halves can be sorted independently

✗ Disadvantages

− O(n) extra space for merging
− Slower than Quick Sort in practice for in-memory sorting due to memory allocation
− Not in-place (requires extra array for merging)

Viva Questions & Answers

Q1. What is the recurrence relation for Merge Sort?

T(n) = 2T(n/2) + O(n). By Master Theorem, this solves to T(n) = O(n log n).

Q2. Why is Merge Sort stable?

In the merge step, when two equal elements are encountered, the one from the left subarray is placed first, preserving relative order.

Q3. When is Merge Sort preferred over Quick Sort?

When stability is required, for linked lists (no extra space needed), for external sorting, and when worst-case O(n log n) guarantee is needed.

Q4. What is external sorting and why is Merge Sort suited for it?

External sorting handles data that doesn't fit in memory (on disk). Merge Sort naturally merges sorted chunks, making it ideal for sequential disk access.

Q5. How many levels of recursion does Merge Sort have?

O(log n) levels, since the array is halved at each level.