Implement and optimize Java's merge sort algorithm

Implementation and Optimization of Java Merge Sort Algorithm

Merge sort is a sorting algorithm based on comparison. Its main idea is to divide the sequence to be sorted into several sub- Sequence, sort each subsequence, and finally merge the ordered subsequences into an overall ordered sequence.

1. Implementation of the merge sort algorithm:
   The implementation of the merge sort algorithm can be divided into two steps: divide and conquer and merge.

(1) Divide and Conquer:
First, divide the sequence to be sorted into two parts until each subsequence has only one element. Then, these subsequences are merged into ordered subsequences.

The following is a sample code of a recursive implementation of the merge sort algorithm:

public class MergeSort {
    // 归并排序
    public void mergeSort(int[] array, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            // 递归地对左右两边进行归并排序
            mergeSort(array, left, mid);
            mergeSort(array, mid + 1, right);
            // 合并两个有序子序列
            merge(array, left, mid, right);
        }
    }

    // 合并两个有序子序列
    public void merge(int[] array, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        int i = left; // 左序列指针
        int j = mid + 1; // 右序列指针
        int k = 0; // 临时数组指针

        while (i <= mid && j <= right) {
            if (array[i] <= array[j]) {
                temp[k++] = array[i++];
            } else {
                temp[k++] = array[j++];
            }
        }

        while (i <= mid) {
            temp[k++] = array[i++];
        }

        while (j <= right) {
            temp[k++] = array[j++];
        }

        for (int l = 0; l < temp.length; l++) {
            array[left + l] = temp[l];
        }
    }
}

(2) Merge:
The function of the merge function is to merge two ordered subsequences into one ordered sequence. In the specific implementation, we need to create a temporary array to store the merged results. When traversing a subsequence, we compare the elements in the subsequence, put the smaller element into a temporary array, and move the corresponding pointer. Finally, the elements in the temporary array are copied back to the original array.

2. Optimization of the merge sort algorithm:
   The merge sort algorithm will generate many temporary subsequence arrays during the recursive process, which will lead to frequent allocation and release of memory, increasing the space complexity of the algorithm. Spend. In order to reduce this overhead, the efficiency of the merge sort algorithm can be improved through the following optimization methods:

(1) Use insertion sort for small-scale subsequences:
When the size of the subsequence is relatively small , insertion sort is more efficient. Therefore, during the recursive process of merge sort, when the size of the subsequence is less than a certain threshold, insertion sort can be used to replace the recursive process.

public void mergeSort(int[] array, int left, int right) {
    if (left < right) {
        if (right - left <= THRESHOLD) {
            // 子序列的规模小于阈值，采用插入排序
            insertionSort(array, left, right);
        } else {
            int mid = (left + right) / 2;
            mergeSort(array, left, mid);
            mergeSort(array, mid + 1, right);
            merge(array, left, mid, right);
        }
    }
}

(2) Optimize the merging process:
During the merging process, you can first store the two subsequences in two temporary arrays, and then merge the two temporary arrays into the original array. . This way you avoid repeatedly creating temporary arrays during the merge process. At the same time, since the size of the temporary array is fixed, it can be defined as a member variable of the class to avoid repeated creation during the recursive process.

public class MergeSort {
    private int[] temp;

    public void mergeSort(int[] array, int left, int right) {
        if (left < right) {
            if (right - left <= THRESHOLD) {
                insertionSort(array, left, right);
            } else {
                int mid = (left + right) / 2;
                mergeSort(array, left, mid);
                mergeSort(array, mid + 1, right);
                merge(array, left, mid, right);
            }
        }
    }

    public void merge(int[] array, int left, int mid, int right) {
        int i = left;
        int j = mid + 1;
        int k = 0;

        while (i <= mid && j <= right) {
            if (array[i] <= array[j]) {
                temp[k++] = array[i++];
            } else {
                temp[k++] = array[j++];
            }
        }

        while (i <= mid) {
            temp[k++] = array[i++];
        }

        while (j <= right) {
            temp[k++] = array[j++];
        }

        for (int l = 0; l < k; l++) {
            array[left + l] = temp[l];
        }
    }
}

To sum up, the above is the implementation of Java merge sort algorithm and its optimization method. By optimizing the merging process and using insertion sort for small-scale subsequences, the efficiency of the merge sort algorithm can be improved and the space overhead can be reduced. In practical applications, choosing appropriate optimization methods and making reasonable choices based on the characteristics of the sorting sequence can make the algorithm more efficient.

The above is the detailed content of Implement and optimize Java's merge sort algorithm. For more information, please follow other related articles on the PHP Chinese website!