#merge-sort-algorithm-c-python-java-example-Data-Structures

Implementation of Merge Sort in C: A Comprehensive Guide

Updated: 13/08/2023 by Computer Hope

Merge Sort is one of the most efficient and widely used sorting algorithms in data structures. It is based on the Divide and Conquer strategy, making it a popular choice for sorting large datasets. In this article, we will dive deep into how to implement Merge Sort in C, along with Java and Python examples, making it an all-in-one resource for developers and learners.

What is Merge Sort?

Merge Sort is a Divide and Conquer algorithm that works by:

1. Dividing the input array into two halves.
2. Recursively sorting the two halves.
3. Merging the sorted halves back into one.

The merge() function plays a critical role in combining two sorted subarrays into a single sorted array.

Why Use Merge Sort?

• Stability: Maintains the relative order of records with equal keys.
• Time Complexity:
  • Best, Average, and Worst Case: O(n log n)
• Use Case: Ideal for large datasets where quick sorting is required.

Merge Sort in C

Below is a detailed implementation of Merge Sort in C:

#include<stdio.h>
#define MAX 50

void mergeSort(int arr[], int low, int mid, int high);
void partition(int arr[], int low, int high);

int main() {
    int merge[MAX], i, n;

    printf("Enter the total number of elements: ");
    scanf("%d", &n);

    printf("Enter the elements to be sorted: ");
    for (i = 0; i < n; i++) {
        scanf("%d", &merge[i]);
    }

    partition(merge, 0, n - 1);

    printf("After merge sorting, the elements are: ");
    for (i = 0; i < n; i++) {
        printf("%d ", merge[i]);
    }

    return 0;
}

void partition(int arr[], int low, int high) {
    int mid;

    if (low < high) {
        mid = (low + high) / 2;
        partition(arr, low, mid);
        partition(arr, mid + 1, high);
        mergeSort(arr, low, mid, high);
    }
}

void mergeSort(int arr[], int low, int mid, int high) {
    int i, m, k, l, temp[MAX];

    l = low;
    i = low;
    m = mid + 1;

    while ((l <= mid) && (m <= high)) {
        if (arr[l] <= arr[m]) {
            temp[i] = arr[l];
            l++;
        } else {
            temp[i] = arr[m];
            m++;
        }
        i++;
    }

    if (l > mid) {
        for (k = m; k <= high; k++) {
            temp[i] = arr[k];
            i++;
        }
    } else {
        for (k = l; k <= mid; k++) {
            temp[i] = arr[k];
            i++;
        }
    }

    for (k = low; k <= high; k++) {
        arr[k] = temp[k];
    }
}

Output:

• Input: Enter the elements [12, 11, 13, 5, 6, 7]
• Result: [5, 6, 7, 11, 12, 13]

Merge Sort in Java

Here’s an example of Merge Sort implemented in Java:

class MergeSort {
    void merge(int arr[], int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;

        int leftArr[] = new int[n1];
        int rightArr[] = new int[n2];

        for (int i = 0; i < n1; i++) {
            leftArr[i] = arr[left + i];
        }
        for (int j = 0; j < n2; j++) {
            rightArr[j] = arr[mid + 1 + j];
        }

        int i = 0, j = 0, k = left;

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

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

        while (j < n2) {
            arr[k] = rightArr[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);
        }
    }

    static void displayArray(int arr[]) {
        for (int element : arr) {
            System.out.print(element + " ");
        }
        System.out.println();
    }

    public static void main(String args[]) {
        int arr[] = {12, 11, 13, 5, 6, 7};
        System.out.println("Given Array:");
        displayArray(arr);

        MergeSort ob = new MergeSort();
        ob.mergeSort(arr, 0, arr.length - 1);

        System.out.println("\nSorted Array:");
        displayArray(arr);
    }
}

Merge Sort in Python

Python implementation of Merge Sort is concise yet powerful:

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        left_half = arr[:mid]
        right_half = arr[mid:]

        merge_sort(left_half)
        merge_sort(right_half)

        i = j = k = 0

        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1

        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1

        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1

def display(arr):
    for element in arr:
        print(element, end=" ")
    print()

arr = [12, 11, 13, 5, 6, 7]
print("Given Array:")
display(arr)

merge_sort(arr)
print("Sorted Array:")
display(arr)

Conclusion

Merge Sort is a fundamental sorting algorithm that finds its application in various domains due to its stability and efficiency. Whether you are coding in C, Java, or Python, understanding Merge Sort is essential for anyone diving into algorithms and data structures.