Merge sort learning

Merge Sort

Merge sort is an efficient sorting algorithm based on merge operation. This algorithm is a very typical application of Divide and Conquer. The ordered subsequences are combined to obtain a fully ordered sequence. That is, each subsequence is ordered first, and then the subsequence segments are ordered. If two ordered tables are joined into one ordered table, it is called 2-way merge.

Algorithm description

1. The input sequence of length N is divided into two subsequences of length N /2.
2. Merge sort is used for these two subsequences respectively.
3. Combine two sorted subsequences into a final sorted sequence.

example

Array:3  17  12  11  2  20  27  23Divided into two groups:3  17  12  11  | 2  20  27  23Each group is divided into:3  17 ； 12  11 | 2  20 ； 27  23For the first time:3  17  12  11  2  20  27  23The second:3  17  11  12  2  20  27  23The third time:3  11  12  17  2  20  27  23For the fourth time:3  11  12  17  2  20  27  23Fifth:3  11  12  17  2  20  23  27Sixth:3  11  12  17  2  20  23  27Seventh:2  3  11  12  17  20  23  27The end of theCopy the code

Algorithm complexity

Space complexity: O(n)

Time complexity:

The sorting is stable, and the first two parameters that are equal are still the first.

Code implementation

 public static int[] sort(int[] sourceArray) throws Exception {
     int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
     if (arr.length < 2) {
         return arr;
     }
     int middle = (int) Math.floor(arr.length / 2);
     int[] left = Arrays.copyOfRange(arr, 0, middle);
     int[] right = Arrays.copyOfRange(arr, middle, arr.length);
     return merge(sort(left), sort(right));
 }

private static int[] merge(int[] left, int[] right) {
    int[] result = new int[left.length + right.length];
    int i = 0;
    while (left.length > 0 && right.length > 0) {
        if (left[0] <= right[0]) {
            result[i++] = left[0];
            left = Arrays.copyOfRange(left, 1, left.length);
        } else {
            result[i++] = right[0];
            right = Arrays.copyOfRange(right, 1, right.length); }}while (left.length > 0) {
        result[i++] = left[0];
        left = Arrays.copyOfRange(left, 1, left.length);
    }
    while (right.length > 0) {
        result[i++] = right[0];
        right = Arrays.copyOfRange(right, 1, right.length);
    }
    System.out.println(Arrays.toString(result));
    return result;
}
Copy the code

The results

Input array:int[] arr = {3.17.12.11.2.20.27.23};
[3.17]
[11.12]
[3.11.12.17]
[2.20]
[23.27]
[2.20.23.27]
[2.3.11.12.17.20.23.27]
Copy the code

But following the steps above, at this point we can see that the results are consistent.