求Merge sort算法Java实现的详细代码讲解链接

Hey there! Let's break down the Java implementation of Merge Sort step by step so every condition and loop makes total sense to you.

First, here's the full working code, and we'll unpack every part right after:

public class MergeSort {
    // Main method to start the sorting process
    public static void mergeSort(int[] arr) {
        // Base case: arrays with 0 or 1 element are already sorted
        if (arr.length <= 1) {
            return;
        }

        // Split the array into two halves
        int mid = arr.length / 2;
        int[] left = new int[mid];
        int[] right;

        // Handle even vs odd-length arrays for the right half
        if (arr.length % 2 == 0) {
            right = new int[mid];
        } else {
            right = new int[mid + 1];
        }

        // Fill the left half with the first half of the original array
        for (int i = 0; i < mid; i++) {
            left[i] = arr[i];
        }

        // Fill the right half with the remaining elements
        for (int i = 0; i < right.length; i++) {
            right[i] = arr[mid + i];
        }

        // Recursively sort both halves
        mergeSort(left);
        mergeSort(right);

        // Merge the sorted halves back into one sorted array
        merge(arr, left, right);
    }

    // Helper method to merge two sorted arrays into one sorted array
    private static void merge(int[] result, int[] left, int[] right) {
        int leftIdx = 0;
        int rightIdx = 0;
        int resultIdx = 0;

        // Compare elements from both halves and add the smaller one to the result
        while (leftIdx < left.length && rightIdx < right.length) {
            if (left[leftIdx] < right[rightIdx]) {
                result[resultIdx] = left[leftIdx];
                leftIdx++;
            } else {
                result[resultIdx] = right[rightIdx];
                rightIdx++;
            }
            resultIdx++;
        }

        // Add any leftover elements from the left half (if there are any)
        while (leftIdx < left.length) {
            result[resultIdx] = left[leftIdx];
            leftIdx++;
            resultIdx++;
        }

        // Add any leftover elements from the right half (if there are any)
        while (rightIdx < right.length) {
            result[resultIdx] = right[rightIdx];
            rightIdx++;
            resultIdx++;
        }
    }

    // Helper to print arrays (for testing)
    public static void printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] sampleArr = {12, 11, 13, 5, 6, 7};
        System.out.println("Original array:");
        printArray(sampleArr);

        mergeSort(sampleArr);

        System.out.println("Sorted array:");
        printArray(sampleArr);
    }
}

Now let's walk through every key part:

1. The mergeSort Method (Recursive Splitting) #

• Base Case Check: if (arr.length <= 1) return;
  This stops the recursion. If an array has 0 or 1 element, it's already sorted—no need to split it further. Super straightforward, right?

• Splitting the Array:

  • int mid = arr.length / 2;
    Finds the middle point to split the array. For even-length arrays, it's exactly half; for odd arrays, the left half will be one element shorter than the right.
  • The if-else for the right array:
    This fixes the odd-length array issue. For example, if the original array has 5 elements, mid becomes 2, so the left array is size 2, and the right array needs to be size 3 to hold the remaining elements.

• Populating Left & Right Halves:

  • First loop: Copies the first mid elements from the original array into the left half. No overlap here—we're just splitting the array cleanly.
  • Second loop: Copies elements starting at mid (the end of the left half) to the end of the original array into the right half. mid + i ensures we don't re-copy elements from the left.

• Recursive Calls:

  • mergeSort(left); and mergeSort(right);
    We keep splitting each half until we hit the base case (arrays of size 1). Then we start merging those tiny sorted arrays back together.

2. The merge Method (Combining Sorted Halves) #

This is where we stitch the sorted halves back into one sorted array. Let's break each loop:

• Index Initialization:

  • leftIdx, rightIdx: Track our current position in the left and right sorted arrays.
  • resultIdx: Tracks where we place elements in the original (result) array.

• First While Loop: while (leftIdx < left.length && rightIdx < right.length)
  This runs as long as there are elements left in both halves. We compare the current elements from each half:

  • If the left element is smaller, we add it to the result and move the left index forward.
  • Otherwise, we add the right element and move the right index forward.
  • We increment resultIdx every time to make space for the next element.

• Second While Loop: while (leftIdx < left.length)
  If there are leftover elements in the left half (this happens when the left array had more elements, or its last elements were larger than the right's), we add all of them to the result. Since the left array is already sorted, we can just append them in order.

• Third While Loop: while (rightIdx < right.length)
  Same logic as the second loop, but for the right half. This catches any remaining elements that didn't get added in the first loop.

3. Testing the Code #

The main method sets up a sample array, prints the original version, runs mergeSort, then prints the sorted result. You can tweak the sample array to test edge cases (like odd-length, reverse-sorted, or already sorted arrays) to see how the algorithm handles them.

If any part still feels unclear, just let me know—I can dive deeper into specific lines or logic!

内容的提问来源于stack exchange，提问作者John R.