Data Structures and Algorithms - Merge Sort - Day 7

Merge Sort

Merge sort uses the divide and conqur approach to sort an array.

Algorithm

In mergesort we divide the array in half, then apply mergesort to the halves. We do this until 1 element reached. Then we have to merge the arrays. While merging we take two pointers comparing the two elements and merging in order.

Example

Starting array -

9 7 2 1 3 10 11 5

Two parts -

9 7 2 1


3 10 11 5

Parting again -

9 7

2 1


3 10

11 5

Parting again -

9
7

2
1

3
10

11
5

Now mergin the parts -

7 9

1 2


3 10

5 11

Now mergin again -

1 2 7 9


3 5 10 11

Now merging -

1 2 3 5 7 9 10 11

Code in C

#include <stdio.h>

void merge(int arr[], int l, int m, int r){
    // indexes required for traversal
    int i,j,k;
    //find the size of the left and right part
    int n1 = m - l + 1;
    int n2 = r - m;
    // create two  temporary arrays
    int L[n1],R[n2];
    //copy the elements in the array
    for(i = 0; i < n1; i++){
        L[i] = arr[l+i];
    }
    for(i = 0; i < n2; i++){
        R[i] = arr[m+i+1];
    }
    //merge the left and right array
    i = l;
    j = 0;
    k = 0;
    while(j < n1 && k < n2){
        if(L[j] < R[k]){
            arr[i] = L[j];
            j++;
        }
        else{
            arr[i] = R[k];
            k++;
        }
        i++;
    }

    // copy the residual elements
    while(j<n1){
        arr[i] = L[j];
        i++;
        j++;
    }

    while(k<n2){
        arr[i] = R[k];
        i++;
        k++;
    }
}

void mergesort(int arr[], int l, int r) {
    if (l < r) {
        int m = (l + r)/ 2;
        mergesort(arr, l, m);
        mergesort(arr, m+1, r);
        merge(arr, l, m, r);
    }
}


int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = 6;

    mergesort(arr, 0, n - 1);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}

Time and space complexity

Best, average and worst case time complexity - O(n log(n))

Best, average and worst case space complexity - O(n) because of the temporary arrays used for merging.