Merge sort

Introduction:

This is a comparison based sort where we use divide and conquer method to sort the array of n numbers

Problem Statement:

Sort an array of n integers

Algorithm

1. we have an array of n numbers.

2. mergesort of an array divides the array into two parts and call mergesort on each and then merges them together calling "merge(..)"

3. we end recursion in mergesort if array size is 1. see the following image for an instance of this method

Pseudo code :

merge_sort(a[], start, end):
    mid = (start+end)/2
    merge_sort(a, start, mid)
    merge_sort(a, mid+1, end)
    merge(a, start, end, mid)

merge(a, start, end, mid):
    left_size = mid - start + 1
    right_size = end - mid
    for i = 0 to left_size:
        left[i] = a[start+i]
    for i = 0 to right_size:
        right[i] = a[mid+1+i]
    i = 0
    j = 0
    k = start
    while i < left_size and j < right_size:
        if left[i] <= right[j]:
            a[k] = left[i]
            i++
        else:
            a[k] = right[j]
            j++
        k++
    while i < left_size:
        a[k] = left[i]
        k++
    while j < right_size:
        a[k] = right[j]
        k++
        j++

Code :

    #include <bits/stdc++.h>
    using namespace std;
    
    void merge(int a[], int start, int end, int mid)
    {
        int left_size = (mid - start) + 1;
        int right_size = end - mid;
    
        int left[left_size];
        int right[right_size];
    
        for (int i = 0; i < left_size; i++) // copy a[start...mid] into left
        {
            left[i] = a[start + i];
        }
        for (int i = 0; i < right_size; i++) // copy a[mid+1...end] into right
        {
            right[i] = a[mid + 1 + i];
        }
    
        int i = 0, j = 0, k = start;
        while (i < left_size && j < right_size) // merging left and right into a[start....end]
        {
            if (left[i] <= right[j]) // if equal you can compare based on another logic.
            {
                a[k] = left[i];
                i++;
            }
            else
            {
                a[k] = right[j];
                j++;
            }
            k++;
        }
        while (i < left_size) //leftover elements
        {
            a[k] = left[i];
            k++;
            i++;
        }
        while (j < right_size) // leftover elements
    
        {
            a[k] = right[j];
            k++;
            j++;
        }
    }
    
    
    void merge_sort(int a[], int start, int end)
    {
        if (end <= start)
        {
            return;
        }
        int mid = (start + end) / 2; //get mid
    
        merge_sort(a, start, mid);   // call merge_sort on left
        merge_sort(a, mid + 1, end); //call merge_sort on right
        merge(a, start, end, mid);   // merge
    }
    
    
    int main()
    {
        int n;
        cout << "Enter n: ";
        cin >> n;
        int a[n];
        for (int i = 0; i < n; i++)
        {
            cin >> a[i];
        }
        merge_sort(a,0,n-1);
        for (int i = 0; i < n; i++)
        {
            cout << a[i] << " ";
        }
        printf("\n");
    }

Complexity Analysis :

The complexity is \(O(nlogn)\).

This can be proved using Master theorem for getting time complexities of divide and conquer algorithms