Merge sort is a popular sorting algorithm that follows the divide-and-conquer approach. It divides the input array into two halves, sorts each half separately, and then merges the sorted halves to obtain the final sorted array. It is known for its stable sorting and has a time complexity of O(n log n).

Here's an explanation of the merge sort algorithm:

1. Divide the unsorted array into two halves by finding the middle element.

2. Recursively sort the left half of the array.

3. Recursively sort the right half of the array.

4. Merge the two sorted halves to obtain the final sorted array.

Here's an example implementation of the merge sort algorithm in C:

#include <stdio.h>

// Function to merge two sorted sub-arrays into one sorted array
void merge(int arr[], int left[], int leftSize, int right[], int rightSize) {
    int i = 0; // Index for left sub-array
    int j = 0; // Index for right sub-array
    int k = 0; // Index for merged array

    // Compare elements from the left and right sub-arrays and merge them
    while (i < leftSize && j < rightSize) {
        if (left[i] <= right[j]) {
            arr[k++] = left[i++];
        } else {
            arr[k++] = right[j++];
        }
    }

    // Copy the remaining elements of the left sub-array, if any
    while (i < leftSize) {
        arr[k++] = left[i++];
    }

    // Copy the remaining elements of the right sub-array, if any
    while (j < rightSize) {
        arr[k++] = right[j++];
    }
}

// Function to perform merge sort
void mergeSort(int arr[], int size) {
    if (size <= 1) {
        return; // Base case: array is already sorted
    }

    int mid = size / 2; // Find the middle index

    // Create left and right sub-arrays
    int left[mid];
    int right[size - mid];

    // Copy elements into left and right sub-arrays
    for (int i = 0; i < mid; i++) {
        left[i] = arr[i];
    }
    for (int i = mid; i < size; i++) {
        right[i - mid] = arr[i];
    }

    // Recursively sort the left and right sub-arrays
    mergeSort(left, mid);
    mergeSort(right, size - mid);

    // Merge the sorted sub-arrays
    merge(arr, left, mid, right, size - mid);
}

// Function to print an array
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
        printf("\n");
    }

    // Test the algorithm
    int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int size = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: ");
    printArray(arr, size);

    mergeSort(arr, size);

    printf("Sorted array: ");
    printArray(arr, size);

    return 0;
}

In this example, the `merge` function is used to merge two sorted sub-arrays into one sorted array. The `mergeSort` function performs the merge sort algorithm recursively on the given array. The `printArray` function is used to display the array before and after sorting.

The output will be:

Original array: 64 34

Time Complexity

The time complexity of the Merge Sort algorithm is O(n log n) in all cases, including the worst, best, and average cases.

In the Merge Sort algorithm, the input array is divided into halves recursively until each half contains only one element. This recursive splitting step requires O(log n) operations, where n is the size of the array.

After the recursive splitting, the merging step begins. In the merging step, the algorithm merges the sorted halves to create a single sorted array. The merging process takes linear time, as each element is compared and placed in the correct order. The number of comparisons required for merging is proportional to the size of the input array.

Therefore, the overall time complexity of Merge Sort is O(n log n). The logarithmic factor comes from the recursive splitting of the array into halves, and the linear factor comes from the merging of the sorted halves.

Merge Sort's time complexity of O(n log n) makes it more efficient than algorithms with quadratic time complexity (such as Bubble Sort or Selection Sort) for larger datasets. It is considered one of the efficient sorting algorithms, particularly for large input sizes.

Space Complexity

The space complexity of the Merge Sort algorithm is O(n) because it requires additional space to store the merged array during the merging operation.

In Merge Sort, during the merging step, temporary arrays are created to store the sorted halves before merging them. The size of these temporary arrays is proportional to the size of the input array. As the recursive splitting and merging process continues, multiple temporary arrays are created, each with a size proportional to a portion of the original array.

However, it's important to note that in most implementations of Merge Sort, the temporary arrays are not created for each recursion level separately. Instead, a single auxiliary array is allocated once and reused throughout the merging process. This can be achieved by using in-place merging or by allocating a separate temporary array once and passing it as a parameter to the merge function.

Therefore, the space complexity of Merge Sort is O(n), where n is the size of the input array. The additional space required is proportional to the size of the array, as temporary arrays are created during the merging step. Once the merging is complete and the final sorted array is obtained, the temporary arrays are discarded, and the space complexity is linear with respect to the input size.

About the Author

Silan Software is one of the India's leading provider of offline & online training for Java, Python, AI (Machine Learning, Deep Learning), Data Science, Software Development & many more emerging Technologies.

We provide Academic Training || Industrial Training || Corporate Training || Internship || Java || Python || AI using Python || Data Science etc