Merge Sort Algorithm

In-depth understanding of the merge sort algorithm

The core idea of ​​the merge sort algorithm is the divide and conquer method, that is, "divide and conquer". It recursively divides an array into smaller subarrays until each subarray contains only one element (which is now sorted). It then merges these subarrays into a larger sorted array. It is worth noting that the sorting process occurs during the merge phase, not the split phase.

Algorithm Demonstration

Suppose we have an array to be sorted:

We divide the array into two left and right sub-arrays:

Continue recursive splitting until each subarray has only one element:

Next, merge and sort these subarrays: smaller values ​​on the left, larger values ​​on the right.

Finally sorted:

Code implementation (Java)

The original Java code has some efficiency issues that we can optimize. The improved code is as follows:

import java.util.Arrays;

public static void mergeSort(int[] array) {
    int n = array.length;
    if (n < 2) {
        return;
    }
    int middle = n / 2;
    int[] left = Arrays.copyOfRange(array, 0, middle);
    int[] right = Arrays.copyOfRange(array, middle, n);

    mergeSort(left);
    mergeSort(right);

    int leftIndex = 0;
    int rightIndex = 0;
    int arrayIndex = 0;

    while (leftIndex < left.length || rightIndex < right.length) {
        if (leftIndex < left.length && (rightIndex >= right.length || left[leftIndex] <= right[rightIndex])) {
            array[arrayIndex++] = left[leftIndex++];
        } else {
            array[arrayIndex++] = right[rightIndex++];
        }
    }
}

This optimized code uses the Arrays.copyOfRange() method to copy array elements more efficiently, and simplifies the loop conditions and judgment statements in the merging process, thus improving the readability and efficiency of the code.

Hope this improved explanation and code can help you better understand the merge sort algorithm!

The above is the detailed content of Merge Sort Algorithm. For more information, please follow other related articles on the PHP Chinese website!