Merge Sort | C++ Implementation


Merge sort follows divide-and-conquer approach. It divides an array of n elements into two subarrays of n/2 elements each. Then it sort the two subarrays recursively using merge sort. And then these subarrays are merged to produce a single sorted array.

Mergesort

If the size of the array is even then the size of subarrays is equal and if it is odd then first array has one element more than the second array. The division of array stops when subarrays contain only one element and then merging of subaarrays starts. The arrays are merged in sorted order.

Implementation

Here is the generic implementation of merge and merge_sort function. It sorts array of all datatypes.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
template<class T>
void merge(std::vector<T>& v, int p, int q, int r)
{
    int size1 = q-p+1;
    int size2 = r-q;
    std::vector<T> L(size1);
    std::vector<T> R(size2);

    for(int i = 0; i < size1; i++)
    {
        L[i] = v[p+i];
    }
    for(int j = 0; j < size2; j++)
    {
        R[j]=v[q+j+1];
    }

    int i=0,j=0;
    int k;
    for(k = p; k <= r && i < size1 && j < size2; k++)
    {
        if(L[i] <= R[j])
        {
            v[k] = L[i];
            i++;
        }
        else
        {
            v[k] = R[j];
            j++;
        }
    }
    for(i = i; i < size1; ++i)
    {
        v[k] = L[i];
        k++;
    }

    for(j = j; j < size2; j++)
    {
        v[k] = R[j];
        k++;
    }
}

When merge function is called, two auxiliary vectors L and R are created. L is initialised with elements of left subarray and R is initialised with elements of right subarray. Both subarrays contain one element each. For eg. from the above fig. L contains 5 and R contains 2.


When we merge these subarrays, the smallest element from these subarray is selected and the element is entered in the input array v at index 0. k maintains the index of input array and i and j maintains the index of L and R subarrayarray respectively.

If all the elements of one of the subarray are entered then remaining elements of the another subarrays are entered in the input array since all elements are greater than the last input value. This is done with the help of last two for loops in the above function.

1
2
3
4
5
6
7
8
9
10
11
template<class T>
void merge_sort(std::vector<T>& v, int p, int r)
{
    if(p < r)
    {
        int q = (p+r)/2;
        merge_sort(v, p, q);
        merge_sort(v, q+1, r);
        merge(v, p, q, r);
    }
}

merge_sort recursively calls itself until r is smaller than or equal to p.

Here is the output of merge sort with generic functions.

Mergesort

C++ Implementation of Merge Sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
 #include <iostream>
#include <vector>

template<class T>
void merge(std::vector<T>& v, int p, int q, int r)
{
    int size1 = q-p+1;
    int size2 = r-q;
    std::vector<T> L(size1);
    std::vector<T> R(size2);

    for(int i = 0; i < size1; i++)
    {
        L[i] = v[p+i];
    }
    for(int j = 0; j < size2; j++)
    {
        R[j]=v[q+j+1];
    }

    int i=0,j=0;
    int k;
    for(k = p; k <= r && i < size1 && j < size2; k++)
    {
        if(L[i] <= R[j])
        {
            v[k] = L[i];
            i++;
        }
        else
        {
            v[k] = R[j];
            j++;
        }
    }
    for(i = i; i < size1; ++i)
    {
        v[k] = L[i];
        k++;
    }

    for(j = j; j < size2; j++)
    {
        v[k] = R[j];
        k++;
    }
}

template<class T>
void merge_sort(std::vector<T>& v, int p, int r)
{
    if(p < r)
    {
        int q = (p+r)/2;
        merge_sort(v, p, q);
        merge_sort(v, q+1, r);
        merge(v, p, q, r);
    }
}

int main()
{
    std::vector<int>vec;
    vec.push_back(13);
    vec.push_back(5);
    vec.push_back(7);
    vec.push_back(7);
    vec.push_back(4);
    vec.push_back(2);
    vec.push_back(10);
    int sz = vec.size();
    std::cout << "Entered array : ";
    for(int n = 0; n < sz; n++)
    {
        std::cout << vec[n] <<" ";
    }
    std::cout << "\n";
    std::cout << "Sorted array : ";
    merge_sort(vec, 0, sz-1);
    for(int n = 0; n < sz; n++)
    {
        std::cout << vec[n] << " ";
    }
    std::cout << "\n\n";

    std::vector<char> c;
    c.push_back('d');
    c.push_back('y');
    c.push_back('h');
    c.push_back('l');
    c.push_back('e');
    c.push_back('a');
    int sz1 = c.size();
    std::cout << "Entered array : ";
    for(int n = 0; n < sz1; n++)
    {
        std::cout << c[n] <<" ";
    }
    std::cout << "\n";
    std::cout << "Sorted array : ";
    merge_sort(c, 0, sz1-1);
    for(int n = 0; n < sz1; n++)
    {
        std::cout << c[n] << " ";
    }
    std::cout << "\n\n";

    std::vector<std::string> str;
    str.push_back("car");
    str.push_back("dog");
    str.push_back("apple");
    str.push_back("ball");
    str.push_back("tree");
    int sz2 = str.size();

    std::cout << "Entered array : ";
    for(int n = 0; n < sz2; n++)
    {
        std::cout << str[n] <<" ";
    }
    std::cout << "\n";
    std::cout << "Sorted array : ";
    merge_sort(str, 0, sz2-1);
    for(int n = 0; n < sz2; n++)
    {
        std::cout << str[n] << " ";
    }
    std::cout << "\n";

    return 0;
}

View this code on Github

Get this post in pdf - Merge sort

Reference:
Introduction to Algorithms
The Algorithm Design Manual
Data Structures and Algorithms Made Easy
Competitive Programmer’s Handbook - Antti Laaksonen

You may also like

Selection sort
Insertion Sort
Quicksort
Heapsort