Home | Projects | Notes > Data Structures & Algorithms > Merge Sort: T = O(n logn) , S = O(n)

Merge Sort: T = O(n logn) , S = O(n)

Introduction

• Merge Sort is a divide-and-conquer sorting algorithm that:

  1. Recursively divides the array into halves until single elements remain.

  2. Then merges those halves back together in sorted order.

• Merge sort is a stable, efficient sorting algorithm with a time complexity of O(n log n), making it well-suited for large datasets.

  Technically:

  $$T(n)=O(nlogn+n)$$

   

  • The n log n term comes from dividing the array in half log n times and processing n elements at each level during merging.

  • The extra n term accounts for the total number of splits, but it’s non-dominant, so it's omitted in the final complexity.

• Space complexity is O(n) because merge sort needs additional memory to hold temporary subarrays during merging.

Implementation (C++)

Source (merge_sort.cpp)

x
1
#include <iostream>
2
#include <vector>
3

4
// merge two sorted halves into original array
5
void merge(std::vector<int> &arr, const std::vector<int> &left, const std::vector<int> &right)
6
{
7
    int i = 0;  // index for origiinal array
8
    int l = 0;  // index for left subarray
9
    int r = 0;  // index for right subarray
10

11
    // merge elements of two subarrays
12
    while (l < left.size() && r < right.size())
13
    {
14
        if (left[l] <= right[r])
15
        {
16
            arr[i++] = left[l++];
17
        }
18
        else
19
        {
20
            arr[i++] = right[r++];
21
        }
22
    }
23

24
    // copy remaining elements (only one subarray may ahve leftovers)
25
    while (l < left.size())
26
    {
27
        arr[i++] = left[l++];
28
    }
29
    while (r < right.size())
30
    {
31
        arr[i++] = right[r++];
32
    }
33
}
34

35
// recursive merge sort
36
void merge_sort(std::vector<int> &arr)
37
{
38
    // base case
39
    if (arr.size() <= 1)
40
    {
41
        return;
42
    }
43

44
    int mid = arr.size() / 2;
45

46
    std::vector<int> left(arr.begin(), arr.begin() + mid);  // [arr[0], arr[mid - 1]] 
47
    std::vector<int> right(arr.begin() + mid, arr.end());   // [arr[mid], arr[arr.size() - 1]]
48

49
    // recursive case
50
    merge_sort(left);
51
    merge_sort(right);
52
    merge(arr, left, right);
53
}
54

55
int main(int argc, char *argv[])
56
{
57
    std::vector<int> arr = {5, 2, 9, 1, 5, 6};
58
    merge_sort(arr);
59
    
60
    for (auto &elem : arr)
61
    {
62
        std::cout << elem << " ";
63
    }
64
    
65
    std::cout << std::endl;
66
    
67
    return 0;
68
}

x
1
1 2 5 5 6 9

Implementation (C)

Source (merge_sort.c)

1
#include <stdio.h>
2
#include <stdlib.h>
3

4
// merge two sorted subarrays into the original array
5
void merge(int *arr, const int *left, const int l_size, const int *right, const int r_size)
6
{
7
    int i = 0;  // index for original array 
8
    int l = 0;  // index for left subarray  
9
    int r = 0;  // index for right subarray 
10

11
    // merge elements of two subarrays
12
    while (l < l_size && r < r_size)
13
    {
14
        if (left[l] <= right[r])
15
        {
16
            arr[i++] = left[l++];
17
        }
18
        else
19
        {
20
            arr[i++] = right[r++];
21
        }
22
    }
23

24
    // copy remaining elements (only one subarray may ahve leftovers)
25
    while (l < l_size)
26
    {
27
        arr[i++] = left[l++];
28
    }
29

30
    while (r < r_size)
31
    {
32
        arr[i++] = right[r++];
33
    }
34
}
35

36
// recursive merge sort
37
void merge_sort(int *arr, int size)
38
{
39
    if (size <= 1)
40
    {
41
        return;
42
    }
43

44
    int mid = size / 2;
45

46
    // allocate and copy left and right halves
47
    int *left = (int *)malloc(mid * sizeof(int));
48
    int *right = (int *)malloc((size - mid) * sizeof(int));
49

50
    for (int l = 0; l < mid; ++l)
51
    {
52
        left[l] = arr[l];
53
    }
54

55
    for (int r = mid; r < size; ++r)
56
    {
57
        right[r - mid] = arr[r];
58
    }
59

60
    merge_sort(left, mid);
61
    merge_sort(left, size - mid);
62
    merge(arr, left, mid, right, size - mid);
63

64
    free(left);
65
    free(right);
66
}
67

68
int main(int argc, char *argv[])
69
{
70
    int arr[] = {5, 2, 9, 1, 5, 6};
71
    int size = sizeof(arr) / sizeof(arr[0]);
72

73
    merge_sort(arr, size);
74

75
    for (int i = 0; i < size; ++i)
76
    {
77
        printf("%d ", arr[i]);
78
    }
79

80
    puts("");
81
    
82
    return 0;
83
}

1
1
1 2 5 5 6 9