Merge Sort in C

Working on Merge Sort Algorithm

Now, that we know what Merge sort is, let's take a closer look at how the merge sort algorithm works :
 

1. Divide: If the input list contains more than one element, divide it into two roughly equal sublists.
 

2. Conquer: Recursively apply the merge sort algorithm to each sublist until all sublists contain only one element or are empty. This step involves continuously dividing the sublists into smaller halves until they become trivial to sort.
 

3. Merge: Once the sublists are sorted, merge them back together to form a single sorted list. The merging process involves comparing the elements from each sublist & placing them in the correct order in the merged list.
 

Let’s see a step-by-step example of how merge sort works on the list [5, 2, 4, 7, 1, 3, 2, 6]:
 

1. Divide the list into two halves: [5, 2, 4, 7] & [1, 3, 2, 6].
 

2. Recursively divide the sublists until each sublist contains only one element:

   - [5, 2] & [4, 7]

   - [5] & [2], [4] & [7]

   - [1, 3] & [2, 6]

   - [1] & [3], [2] & [6]
 

3. Merge the sorted sublists back together:

   - Merge [5] & [2] to get [2, 5]

   - Merge [4] & [7] to get [4, 7]

   - Merge [2, 5] & [4, 7] to get [2, 4, 5, 7]

   - Merge [1] & [3] to get [1, 3]

   - Merge [2] & [6] to get [2, 6]

   - Merge [1, 3] & [2, 6] to get [1, 2, 3, 6]

   - Finally, merge [2, 4, 5, 7] & [1, 2, 3, 6] to get the final sorted list: [1, 2, 2, 3, 4, 5, 6, 7]
 

The merging process ensures that the elements are placed in the correct order by comparing them from each sublist & selecting the smaller element to be added to the merged list.

Implementation of Merge Sort in C 

#include <stdio.h>

void merge(int arr[], int left, int mid, int right) {
    int i, j, k;
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int L[n1], R[n2];
    for (i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];

    i = 0;
    j = 0;
    k = left;

    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }


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


void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;


        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);


        merge(arr, left, mid, right);
    }
}


int main() {
    int arr[] = {5, 2, 4, 7, 1, 3, 2, 6};
    int n = sizeof(arr) / sizeof(arr[0]);


    printf("Original array: ");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);


    mergeSort(arr, 0, n - 1);


    printf("\nSorted array: ");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);


    return 0;
}

You can also try this code with Online C Compiler

Run Code

Explanation

1. The `merge` function takes an array `arr`, the left index `left`, the middle index `mid`, & the right index `right` as parameters. It merges two sorted subarrays, `L` & `R`, into a single sorted subarray within `arr`.
 

2. The `mergeSort` function takes an array `arr`, the left index `left`, & the right index `right` as parameters. It recursively divides the array into two halves until the base case (subarray of size 1) is reached. Then, it calls the `merge` function to merge the sorted subarrays.
 

3. In the `main` function, we define an array `arr` & calculate its size `n`. We print the original array, call the `mergeSort` function to sort the array, & finally print the sorted array.

Output:

Original array: 5 2 4 7 1 3 2 6
Sorted array: 1 2 2 3 4 5 6 7

Merge Sort Complexity

Now, Let's analyze the time and space complexity of merge sort:

Time Complexity:

- Best Case: O(n log n)

- Average Case: O(n log n)

- Worst Case: O(n log n)

Explanation

• In merge sort, the array is repeatedly divided into two halves until we reach subarrays of size 1. This division process takes logarithmic time, expressed as log n. Then, the merging process takes linear time, expressed as n, to merge the sorted subarrays back together. Therefore, the overall time complexity of merge sort is O(n log n) in all cases, regardless of the initial order of the input.
   
• The best case, average case, and worst case time complexities are all the same for merge sort because the algorithm always divides the array into two halves and performs the same number of comparisons and merges, regardless of the input's initial order.

Space Complexity

- Auxiliary Space: O(n)

- Total Space: O(n)

Explanation

• Merge Sort requires O(n) additional space to store temporary subarrays during the merging process. The size of these temporary arrays is proportional to the input array size. While the recursive calls require O(log n) space, the dominant factor is the O(n) space needed for merging.
   
• The O(n) space complexity can be a limitation when working with large datasets and limited memory. However, Merge Sort's efficient O(n log n) time complexity often makes it a preferred choice despite the space trade-off.

Advantages of Merge Sort

1. Efficient for Large Data: Merge sort is great for big lists because it always sorts data in O(n log n) time, which means it sorts faster as the amount of data grows.
    
2. Keeps Order Stable: It keeps the original order of the same elements as they were before sorting. This is useful when the sequence of data matters.
    
3. Consistent Performance: No matter if the data is already sorted, partially sorted, or completely mixed up, Merge sort works in the same amount of time, making it a reliable choice.
    
4. Good for Complex Problems: It breaks the sorting task into smaller pieces, making complex sorting problems simpler to handle. This method is good for using multiple processors or machines to speed up sorting.
    
5. Works with External Data: Merge sort is good for sorting huge data sets that can't fit all at once in the computer's memory. It can manage and merge chunks of data stored elsewhere.
    
6. Easy to Understand: The logic behind Merge sort is straightforward, making it easier to learn and use than some other more complicated sorting methods.

Disadvantages of Merge Sort

1. Needs Extra Space: It requires more memory because it has to make new arrays to hold data temporarily while sorting.
    
2. Uses Recursion: The recursive nature of Merge sort can take up a lot of memory and might cause errors if the data set is very large.
    
3. Not Memory Efficient: Since it’s not an in-place sorting algorithm, it needs additional space which might be a problem when memory is limited.
    
4. Slower for Small Data: For small amounts of data, Merge sort might be slower compared to simpler sorting methods because of its setup and recursive sorting steps.
    
5. Setup Takes Time: Every time Merge sort splits data, it has to set up new arrays for temporary storage which can slow things down a bit.
    
6. Doesn't Adapt: Merge sort doesn’t adjust based on the data’s initial order. It performs the same steps whether the data is nearly sorted already or completely unorganized.

Frequently Asked Questions

Is merge sort an in-place sorting algorithm?

No, merge sort is not an in-place sorting algorithm. It requires additional space of O(n) to store the temporary subarrays during the merging process.

Can merge sort be implemented iteratively?

Yes, merge sort can be implemented iteratively using a bottom-up approach. Instead of using recursion, the iterative version starts with subarrays of size 1 and iteratively merges them until the entire array is sorted.

Is merge sort stable?

Yes, merge sort is a stable sorting algorithm. It preserves the relative order of equal elements during the sorting process.

What is the formula for merge sort?

The formula for Merge Sort is a recurrence relation: T(n)=2T(n/2)+O(n), where T(n/2) represents sorting the two halves, and O(n) is for merging. Solving it gives a time complexity of O(nlogn), efficient for large datasets.

Conclusion

In this article, we explained the merge sort algorithm, a popular and efficient sorting technique. We discussed its divide-and-conquer approach, which recursively divides the input array into smaller subarrays until they become trivial to sort, and then merges them back together to obtain the final sorted array. We also provided a detailed implementation of merge sort in C, along with a step-by-step explanation of its working principle. Additionally, we analyzed the advantages and disadvantages of merge sort and lastly we analyzed the time and space complexity of the Merge sort algorithm.