Merge Sort Algorithm - Java, C, and Python Implementation

Merge Sort is a classic sorting algorithm known for its efficiency and stability. It belongs to the category of divide and conquer algorithms, making it suitable for sorting large datasets. This tutorial will guide you through implementing Merge Sort in Java, C, and Python, providing insights into its time complexity, space complexity, and best practices.

Merge Sort Algorithm Overview

Merge Sort operates by recursively dividing the input array into smaller subarrays until each subarray contains only one element. It then merges these subarrays in a sorted manner until the entire array is sorted. This approach ensures a time complexity of O(n log n) in the average and worst cases, making Merge Sort a preferred choice for various applications.

Merge Sort Implementation in Java

Merge Sort is a classic divide-and-conquer algorithm used for sorting an array or a list. It works by dividing the array into two halves, recursively sorting each half, and then merging the sorted halves to produce the sorted output.

Below is a simple Java implementation of Merge Sort:

Step 1: Define the Merge Sort Function

public class MergeSort {
    // This method sorts the array from index 'left' to 'right' using merge sort algorithm
    public void mergeSort(int[] array, int left, int right) {
        // Base condition to end recursion
        if (left < right) {
            // Calculate the midpoint of the array
            int mid = left + (right - left) / 2;

            // Recursively sort the first half
            mergeSort(array, left, mid);

            // Recursively sort the second half
            mergeSort(array, mid + 1, right);

            // Merge the two sorted halves
            merge(array, left, mid, right);
        }
    }
    
    // This method merges two subarrays of 'array'.
    // First subarray is array[left..mid]
    // Second subarray is array[mid+1..right]
    private void merge(int[] array, int left, int mid, int right) {
        // Calculate the sizes of the two subarrays to be merged
        int n1 = mid - left + 1;
        int n2 = right - mid;

        // Create temporary arrays for left and right subarrays
        int[] leftArray = new int[n1];
        int[] rightArray = new int[n2];

        // Copy data to temporary arrays
        for (int i = 0; i < n1; ++i)
            leftArray[i] = array[left + i];
        for (int j = 0; j < n2; ++j)
            rightArray[j] = array[mid + 1 + j];
        
        // Initial indexes of the first and second subarrays
        int i = 0, j = 0;

        // Initial index of the merged subarray
        int k = left;

        // Merge the temporary arrays back into the original array
        while (i < n1 && j < n2) {
            // Compare elements from leftArray and rightArray and copy the smaller element to the original array
            if (leftArray[i] <= rightArray[j]) {
                array[k] = leftArray[i];
                i++;
            } else {
                array[k] = rightArray[j];
                j++;
            }
            k++;
        }
        
        // Copy any remaining elements of leftArray, if any
        while (i < n1) {
            array[k] = leftArray[i];
            i++;
            k++;
        }
        
        // Copy any remaining elements of rightArray, if any
        while (j < n2) {
            array[k] = rightArray[j];
            j++;
            k++;
        }
    }
}

Step 2: Implement Merge Sort in Main Class

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] array = { 12, 11, 13, 5, 6, 7 };  // Initialize the array to be sorted
        MergeSort sorter = new MergeSort();    // Create an instance of the MergeSort class
        sorter.mergeSort(array, 0, array.length - 1);  // Call the mergeSort method on the array
        System.out.println("Sorted array: " + Arrays.toString(array));  // Print the sorted array
    }
}

Output:

Merge Sort Implementation in C

Merge Sort is an efficient sorting algorithm suitable for large datasets due to its O(n log n) time complexity. The C implementation provided demonstrates the core principles of the algorithm and can be adapted for more complex applications.

The C implementation follows a similar logic to Java but with syntax differences.

Define the Merge Sort Function

  #include 

// Function to merge two halves of the array
void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1; // Size of the left subarray
    int n2 = r - m;     // Size of the right subarray

    int L[n1], R[n2];   // Temporary arrays to hold the two halves

    // Copy data to temporary arrays L[] and R[]
    for (int i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];

    int i = 0, j = 0, k = l; // Initial indices of the subarrays and merged array

    // Merge the temporary arrays back into arr[l..r]
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    // Copy the remaining elements of L[], if any
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    // Copy the remaining elements of R[], if any
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

// Function to implement MergeSort
void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2; // Find the middle point

        // Sort first and second halves
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);

        // Merge the sorted halves
        merge(arr, l, m, r);
    }
}

int main() {
    int arr[] = { 12, 11, 13, 5, 6, 7 }; // Input array
    int n = sizeof(arr) / sizeof(arr[0]); // Calculate the number of elements in the array

    // Call mergeSort on the array
    mergeSort(arr, 0, n - 1);

    // Print the sorted array
    printf("Sorted array: ");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");

    return 0; // End of the program
}

Output:

Merge Sort Implementation in Python

Python offers a concise syntax for implementing Merge Sort.

Define the Merge Sort Function

def merge_sort(arr):
    # If the array has more than one element, it can be split and sorted
    if len(arr) > 1:
        mid = len(arr) // 2  # Find the middle point to divide the array
        left_half = arr[:mid]  # Left half from start to middle
        right_half = arr[mid:]  # Right half from middle to end
        
        # Recursively sort the two halves
        merge_sort(left_half)
        merge_sort(right_half)
        
        i = j = k = 0  # Initialize pointers for left_half (i), right_half (j), and merged array (k)
        
        # Merge the left and right halves back into the original array
        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
        
        # Copy any remaining elements of left_half, if any
        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1
        
        # Copy any remaining elements of right_half, if any
        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1

# Sample array to be sorted
array = [12, 11, 13, 5, 6, 7]
merge_sort(array)  # Call merge_sort on the array
print("Sorted array:", array)  # Print the sorted array

Output:

Performance Analysis and Complexity

Merge Sort exhibits a time complexity of O(n log n) in all cases. Its space complexity is O(n) due to auxiliary space requirements for merging. These characteristics make Merge Sort efficient for large datasets but may consume more memory compared to in-place sorting algorithms.

Conclusion

In conclusion, Merge Sort is a versatile sorting algorithm suitable for various applications. Its stable performance and predictable time complexity make it a valuable tool in software development.