Sort - merge sort

https://en.wikipedia.org/wiki/Merge_sort

Merge sort

  • Principle: using the idea of divide and conquer and recursion, first split the data into the smallest unit, then merge and sort from the smallest unit, and gradually merge the small partition into the largest partition;
  • The merge sort algorithm does not belong to the in place sort algorithm because it requires additional memory space during the merge operation
  • Stability: in the process of merging, the left partition is the main part in the comparison between the left partition and the right partition. Therefore, the relative position of the same element will not change before and after sorting, which belongs to stable sorting

code implementation

public interface Sort<T extends Comparable<T>> {
    /**
     * Sort the array
     *
     * @param array
     * @param flag  true It represents positive order; false stands for reverse order
     */
    void sort(T[] array, boolean flag);
}

public class MergeSort<T extends Comparable<T>> implements Sort<T> {

    /**
     * @param array
     * @param flag  true It represents positive order; false stands for reverse order
     */
    @Override
    public void sort(T[] array, boolean flag) {
        partition(array, 0, array.length - 1, flag);
    }

    /**
     * Partition operation, partition by calculating the intermediate value
     *
     * @author guoxing
     * @date 2020-09-20 12:42 PM
     * @since
     */
    public void partition(T[] array, int low, int high, boolean flag) {
        if (low >= high) {
            return;
        }
        int mid = low / 2 + high / 2; // for fear of low + high exceed int Scope of,Therefore, division is performed before addition
        partition(array, low, mid, flag); // The left interval contains an intermediate value
        partition(array, mid + 1, high, flag);// Interval does not contain intermediate value
        // Merge partitions
        merge(array, low, mid, high, flag);
    }

    private void merge(T[] array, int low, int mid, int high, boolean flag) {
        // Officially separate the sections of the partition
        // Due to generics T You cannot create objects directly,Therefore, its parent class is used
        int leftLength = mid - low + 1;
        // Left interval [low,mid]
        Comparable[] leftPart = new Comparable[leftLength];
        System.arraycopy(array, low, leftPart, 0, leftLength);
        int rightLength = high - mid;
        // Right interval (mid,high]
        Comparable[] rightPart = new Comparable[rightLength];
        System.arraycopy(array, mid + 1, rightPart, 0, rightLength);

        // Compare the left and right intervals for merging
        // The starting position of the index of the original array to be operated on
        int index = low;
        // Left and right interval traversal start index
        int leftIndex = 0, rightIndex = 0;
        /**
         * When comparing two intervals, as long as one interval is traversed, it means that all the remaining data in the other interval must be greater than or less than the traversed elements
         * For example: [1,2,3] [2,4,5]
         * [1,2,2,3] When the first interval traversal is completed, the remaining elements in the second interval [4,5] are all larger than the traversed elements
         *
         *
         */
        for (; leftIndex < leftLength && rightIndex < rightLength;) {
            Comparable leftData = leftPart[leftIndex];
            Comparable rightData = rightPart[rightIndex];
            if ((flag && leftData.compareTo(rightData) < 1) || (!flag && leftData.compareTo(rightData) > -1)) {
                // Put the data of the left interval into the original array
                array[index++] = (T) leftData;
                leftIndex++;
            } else {
                // Put the data of the right interval into the original array
                array[index++] = (T) rightData;
                rightIndex++;
            }
        }
        // Judge whether there is residual data in the left section
        while (leftIndex < leftLength) {
            // Write the remaining data to the original array
            array[index++] = (T) leftPart[leftIndex++];
        }
        // Judge whether there is residual data in the right section
        while (rightIndex < rightLength) {
            // Write the remaining data to the original array
            array[index++] = (T) rightPart[rightIndex++];
        }
    }

    public static void main(String[] args) {
        Integer[] values = new Integer[]{5, 3, 2, 1};
        Sort<Integer> integerInsertSort = new MergeSort<>();
        integerInsertSort.sort(values, true);
        Stream.of(values).forEach(System.out::print);
        System.out.println();
        integerInsertSort.sort(values, false);
        Stream.of(values).forEach(System.out::print);
    }
}

Partition operation: in fact, there are not many function points for partition operation, and mid is obtained through low and high. One thing to note is that unlike the operation of fast sorting center points, merge sorting will not abandon the center point, but classify the center point as the left partition interval;

Merge operation: the sorting operation of merge sorting is mainly in the merge stage, by creating a new left and right partition array (left partition: [low,mid]; right partition: [mid+1,high]), and copying the elements of the original array to the new partition;

  • The merge operation mainly contains three main pointers. The index mark points to the index position of the original array to be operated, the left partition of leftIndex points to the index position of the original array to be operated (compare and write to the original array), and the right partition of rightIndex points to the index position of the original array to be operated (compare and write to the original array);
  • In the process of traversing the left and right partitions, as long as one partition traverses, the circular operation of the two partitions will be ended. The reason is that the merged partitions are orderly data. For the partitions with remaining elements, the data of the remaining partitions can be written directly from the index position

Code implementation in JDK

JDK 15

java.util.Arrays#mergeSort(java.lang.Object[], java.lang.Object[], int, int, int)

// Recursively sort halves of dest into src
int destLow = low;
int destHigh = high;
low += off;
high += off;
int mid = (low + high) >>> 1;
mergeSort(dest, src, low, mid, -off);
mergeSort(dest, src, mid, high, -off);

// If list is already sorted, just copy from src to dest. This is an
// optimization that results in faster sorts for nearly ordered lists.
if (((Comparable)src[mid-1]).compareTo(src[mid]) <= 0) {
System.arraycopy(src, low, dest, destLow, length);
return;
}

// Merge sorted halves (now in src) into dest
for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
if (q >= high || p < mid && ((Comparable)src[p]).compareTo(src[q])<=0)
dest[i] = src[p++];
else
dest[i] = src[q++];
}
For“
for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
if (q >= high || p < mid && ((Comparable)src[p]).compareTo(src[q])<=0)
dest[i] = src[p++];
else
dest[i] = src[q++];
}
"The analysis of this code is as follows. Remember the particularity of" & & "and" | "
        Integer[] integers = new Integer[15];
        for (int i = 15; i > 0; i--) {
            integers[15 - i] = i;
        }
        // You can vm options Medium increase -Djava.util.Arrays.useLegacyMergeSort=true To debug java.util.Arrays.mergeSort(java.lang.Object[], java.lang.Object[], int, int, int)
        /**
         * Analysis of the following code
         *         // Merge sorted halves (now in src) into dest
         *         for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
         *             if (q >= high || p < mid && ((Comparable)src[p]).compareTo(src[q])<=0)
         *                 dest[i] = src[p++];
         *             else
         *                 dest[i] = src[q++];
         *         }
         *  When partitioning the partition data from [low, high], the left section: [low,mid-1] the right section: [mid,high); compare the left and right partitions
         *  p Is the left interval cursor and q is the right interval cursor
         *  When Q > = high is true, it means that the right interval has been traversed completely, and the 𞓜 used is therefore followed by (P < mid & & ((comparable) SRC [P]) CompareTo (SRC [q]) < = 0) will not be executed. Directly put the remaining elements in the left interval into the original array (dest[i] = src[p + +];)
         *  When Q > = high is false, it means that the right section has not been traversed. If P < mid is true, it means that the left section has not been traversed. Therefore (((comparable) SRC [P]) needs to be executed at this time CompareTo (SRC [q]) < = 0) element comparison judgment
         *  When Q > = high is false, it indicates that the right section has not been traversed. If P < mid is false, it indicates that the left section has been traversed completely and (((comparable) SRC [P]) is used CompareTo (SRC [q]) < = 0) does not need to be executed, but directly writes the remaining elements of the right interval into the original array (dest[i] = src[q + +];)
         *
         *  When the loop ends, the data in the [destLow,destHigh) interval of the original array is completely ordered
         *
         */
        Arrays.sort(integers);

The difference between the source code and the code written by yourself is that it does not create a real left and right partition, but builds a virtual left and right partition through low/mid/high based on a copy array of the original array

"Unfinished to be continued ----- use python+Matplotlib to draw visual animation for the rest"



https://zhuanlan.zhihu.com/p/38157591


  


    

Tags: Algorithm

Posted by chasiv on Sun, 15 May 2022 16:19:44 +0300