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

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

Merge Sort

A divide-and-conquer sorting algorithm that works by repeatedly dividing the unsorted list into smaller sublists, sorting those sublists, and then merging them back together to obtain a sorted list. It employs a recursive approach to sorting.
Merge sort is known for its stable nature and efficient time complexity of O(n logn), making it suitable for larger lists.
Technical speaking,
$T \propto O (n \log n + n)$
The term 'n log n' signifies that we iterate through all 'n' items 'log n' times (representing the recursive depth) during the process of splitting the original array into arrays of size 1 and merging them back into an array of size 'n' recursively.
The last term, 'n,' accounts for the total number of splits required to break down the original array into arrays of size 1 (and, of course, another 'n' for putting them back together). However, this 'n' term is non-dominant and thus dropped, as it has a lesser impact on the overall time complexity.
Merge sort has space complexity of O(n), where "n" is the number of elements in the input array. This is because merge sort requires additional space to store the temporary subarrays during the merging process.

Algorithm

Input: An array of elements to be sorted.
Divide: Divide the input array into two equal (or nearly equal) halves.
Recursion: Recursively apply merge sort on each of the two halves until each subarray contains only one element or is empty.
Merge: Combine the sorted subarrays by merging them. This involves comparing elements from both subarrays and placing them in order in a new temporary array.
Copy Back: Copy the merged elements from the temporary array back into the original array in their correct sorted order.
Repeat: Continue this process, dividing, sorting, merging, and copying, until the entire array is sorted.

Pseudo-code


xxxxxxxxxx
25
1
MergeSort(arr):
2
    if length(arr) <= 1:
3
        return arr
4
        
5
    mid = length(arr) / 2
6
    left = MergeSort(arr[0:mid])
7
    right = MergeSort(arr[mid:end])
8
    
9
    merged = Merge(left, right)
10
    return merged
11
    
12
Merge(left, right):
13
    result = []
14
    while left is not empty and right is not empty:
15
        if left[0] <= right [0]:
16
            result.append(left[0])
17
            left = left[1:]
18
        else
19
            result.append(right[0])
20
            right = right[1:]
21
            
22
    // Append any remaining elements
23
    result.extend(left)
24
    result.extend(right)
25
    return result

Code (C++)


xxxxxxxxxx
68
1
#include <iostream>
2
#include <vector>
3

4
using namespace std;
5

6
// Merge function to combine two sorted arrays
7
vector<int> merge(vector<int>& left, vector<int>& right)
8
{
9
    vector<int> merged;
10
    int leftIdx = 0, rightIdx = 0;
11
    
12
    while (leftIdx < left.size() && rightIdx < right.size())
13
    {
14
        if (left[leftIdx] <= right[rightIdx])
15
        {
16
            merged.push_back(left[leftIdx]);
17
            leftIdx++;
18
        }
19
        else
20
        {
21
            merged.push_back(right[rightIdx]);
22
            rightIdx++;
23
        }
24
    }
25
    
26
    while (leftIdx < left.size())
27
    {
28
        merged.push_back(left[leftIdx]);
29
        leftIdx++;
30
    }
31
    
32
    while (rightIdx < right.size())
33
    {
34
        merged.push_back(right[rightIdx]);
35
        rightIdx++;
36
    }
37
    
38
    return merged;
39
}
40

41
// Merge sort function
42
vector<int> mergeSort(vector<int>& arr)
43
{
44
    if (arr.size() <= 1)
45
        return arr;
46
    
47
    int mid = arr.size() / 2;
48
    vector<int> left(arr.begin(), arr.begin() + mid);   // [0, mid)
49
    vector<int> right(arr.begin() + mid, arr.end());    // [mid, end) == [mid, last idx]
50
    
51
    left = mergeSort(left);
52
    right = mergeSort(right);
53
    
54
    return merge(left, right);
55
}
56

57
int main(void)
58
{
59
    vector<int> arr = {6, 4, 2, 1, 5, 3};
60
    vector<int> sortedArr = mergeSort(arr);
61
    
62
    for (auto val : sortedArr)
63
        cout << val << " ";
64
    
65
    cout << endl;
66
    
67
    return 0;
68
}


xxxxxxxxxx
1
1
1 2 3 4 5 6

Code (C)


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

4
// Merge function to combine two sorted arrays
5
void merge(int arr[], int left[], int leftSize, int right[], int rightSize)
6
{
7
    int leftIdx = 0, rightIdx = 0, idx = 0;
8
    
9
    while (leftIdx < leftSize && rightIdx < rightSize)
10
    {
11
        if (left[leftIdx] <= right[rightIdx])
12
        {
13
            arr[idx] = left[leftIdx];
14
            leftIdx++;
15
        }
16
        else
17
        {
18
            arr[idx] = right[rightIdx];
19
            rightIdx++;
20
        }
21
        
22
        idx ++;
23
    }
24
    
25
    while (leftIdx < leftSize)
26
    {
27
        arr[idx] = left[leftIdx];
28
        leftIdx++;
29
        idx++;
30
    }
31
    
32
    while (rightIdx < rightIdx)
33
    {
34
        arr[idx] = right[rightIdx];
35
        rightIdx++;
36
        idx++;
37
    }
38
}
39

40
// Merge sort function
41
void mergeSort(int arr[], int size)
42
{
43
    if (size <= 1)
44
        return;
45
    
46
    int mid = size / 2;
47
    int *left = (int *)malloc(mid * sizeof(int));
48
    int *right = (int *)malloc((size - mid) * sizeof(int));
49
    
50
    for (int i = 0; i < mid; i++)
51
        left[i] = arr[i];
52
    
53
    for (int i = mid; i < size; i++)
54
        right[i - mid] = arr[i];
55
    
56
    mergeSort(left, mid);
57
    mergeSort(right, size - mid);
58
    merge(arr, left, mid, right, size - mid);
59
    
60
    free(left);
61
    free(right);
62
}
63

64
int main(void)
65
{
66
    int arr[] = {6, 4, 2, 1, 5, 3};
67
    int size = sizeof(arr) / sizeof(arr[0]);
68
    
69
    mergeSort(arr, size);
70
    
71
    for (int i = 0; i < size; i++)
72
        printf("%d ", arr[i]);
73
    
74
    puts("");
75
    
76
    return 0;
77
}


xxxxxxxxxx
1
1
1 2 3 4 5 6