Understanding Merge Sort Algorithm (with Examples in Java)

Merge Sort: A Comprehensive Guide

Merge Sort is a highly efficient sorting algorithm frequently employed in various programming languages, either independently or as part of a hybrid approach. Its foundation lies in the Divide and Conquer paradigm: a problem is broken into smaller subproblems, solved individually, and their solutions combined for the final result. Merge Sort recursively divides the input list into halves, sorts each half, and then merges the sorted halves to produce a fully sorted list.

Understanding the Merge Sort Process

Let's illustrate the Merge Sort process using an example array:

This image depicts the recursive division of the array.

This image shows the merging of sorted subarrays.

Implementing Merge Sort

Below is a Java implementation of the Merge Sort algorithm:

import java.util.Arrays;

public class MergeSortTest {
    public static void main(String[] args){
        int[] arr = {8, 2, 6, 4, 9, 1};
        System.out.println("Unsorted array: " + Arrays.toString(arr));
        mergeSort(arr, 0, arr.length-1);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }

    static void mergeSort(int arr[], int start, int end){
        if (start < end){
            int mid = (start + end) / 2;
            mergeSort(arr, start, mid);
            mergeSort(arr, mid + 1, end);
            merge(arr, start, mid, end);
        }
    }

    static void merge(int arr[], int start, int mid, int end){
        int[] left = new int[(mid - start) + 1];
        int[] right = new int[end - mid];

        for(int i = 0; i <= mid - start; i++)
            left[i] = arr[start + i];
        for(int j = 0; j < end - mid; j++)
            right[j] = arr[mid + 1 + j];

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

        while (i < left.length && j < right.length){
            if(left[i] <= right[j]){
                arr[k] = left[i];
                i++;
            }
            else{
                arr[k] = right[j];
                j++;
            }
            k++;
        }

        while (i < left.length){
            arr[k] = left[i];
            i++;
            k++;
        }

        while (j < right.length){
            arr[k] = right[j];
            j++;
            k++;
        }
    }
}

Code Explanation

The mergeSort method recursively divides the array until subarrays contain only one element. The merge method is crucial; it takes the sorted subarrays and merges them efficiently into a single sorted array. The merging process involves comparing elements from both subarrays and placing the smaller element into the main array.

This image illustrates the merging step.

The output of the code is:

Unsorted array: [8, 2, 6, 4, 9, 1] Sorted array: [1, 2, 4, 6, 8, 9]

Algorithmic Complexity

• Time Complexity: O(n log n) in all cases (best, average, and worst). This is because the divide-and-conquer approach remains consistent regardless of the input array's initial order.
• Space Complexity: O(n) due to the extra space required for temporary arrays during the merge operation.

The above is the detailed content of Understanding Merge Sort Algorithm (with Examples in Java). For more information, please follow other related articles on the PHP Chinese website!