Data-Structures-and-Algorithms/Algorithms/Sorting/mergeSort.cpp at master · Manvityagi/Data-Structures-and-Algorithms · GitHub

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
void merge(int a[], int si, int ei)
{
    int final[1000];
    if (si >= ei)
        return;
    int mid = (si + ei) / 2;
    int i = si;
    int j = mid + 1;
    int k = 0;
    while (i <= mid && j <= ei)
    {
        if (a[i] < a[j])
            final[k++] = a[i++];
        else
            final[k++] = a[j++];
    }
    while (i <= mid)
        final[k++] = a[i++];

    while (j <= ei)
        final[k++] = a[j++];

    for (i = si; i <= ei; i++)
    {
        a[i] = final[i - si];
    }
}

void mergesort(int a[], int si, int ei)
{
    if (si >= ei)
        return;
    int mid = (si + ei) / 2;
    mergesort(a, si, mid);
    mergesort(a, mid + 1, ei);
    merge(a, si, ei);
}

void mergeSort(int a[], int n)
{
    mergesort(a, 0, n - 1);
}