Java sorting algorithm (IX): merge sorting

tip

The text here is mainly reprinted. The idea is nothing more than the idea of partition and rule
//Idea: the idea of divide and conquer is to separate the array into two arrays (the subdivision of the two arrays is the idea of recursion)
//After the two arrays are sorted, they are merged. In the process of merging, it is necessary to open up a new array space to store the merged array
//Array operation is nothing more than pointer or array segmentation. The idea is the same, but the form of code is different.

Pointer [reprint part]

Merge is to merge two (or more) ordered tables into a new ordered table, that is, the sequence to be sorted is divided into several subsequences, and each subsequence is ordered. Then the ordered subsequences are combined into an overall ordered sequence.

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

The merge sort algorithm is stable. The array needs O(n) additional space, and the linked list needs O(log(n)) additional space. The time complexity is O(nlog(n)). The algorithm is not adaptive and does not need random reading of data.

working principle:

1. Apply for space so that its size is the sum of two sorted sequences. The space is used to store the merged sequences

2. Set two pointers. The initial position is the starting position of the two sorted sequences

3. Compare the elements pointed to by the two pointers, select the relatively small element, put it into the merge space, and move the pointer to the next position

4. Repeat step 3 until a pointer reaches the end of the sequence

5. Copy all the remaining elements of another sequence directly to the end of the merged sequence

Code implementation:

public class MergeSortTest {
 
	public static void main(String[] args) {
		int[] data = new int[] { 5, 3, 6, 2, 1, 9, 4, 8, 7 };
		print(data);
		mergeSort(data);
		System.out.println("Sorted array:");
		print(data);
	}
 
	public static void mergeSort(int[] data) {
		sort(data, 0, data.length - 1);
	}
 
	public static void sort(int[] data, int left, int right) {
		if (left >= right)
			return;
		// Find intermediate index
		int center = (left + right) / 2;
		// Recursion on the left array
		sort(data, left, center);
		// Recursion on the right array
		sort(data, center + 1, right);
		// merge
		merge(data, left, center, right);
		print(data);
	}
 
	/**
	 * Merge the two arrays. The first two arrays are in order, and they are still in order after merging
	 * 
	 * @param data
	 *            Array object
	 * @param left
	 *            Index of the first element of the left array
	 * @param center
	 *            The index of the last element of the left array, and center+1 is the index of the first element of the right array
	 * @param right
	 *            Index of the last element of the right array
	 */
	public static void merge(int[] data, int left, int center, int right) {
		// Temporary array
		int[] tmpArr = new int[data.length];
		// Index of the first element of the right array
		int mid = center + 1;
		// Index of the temporary array of third records
		int third = left;
		// Cache the index of the first element of the left array
		int tmp = left;
		while (left <= center && mid <= right) {
			// Take the smallest from the two arrays and put it into the temporary array
			if (data[left] <= data[mid]) {
				tmpArr[third++] = data[left++];
			} else {
				tmpArr[third++] = data[mid++];
			}
		}
		// The rest is put into the temporary array in turn (in fact, only one of the two while will be executed)
		while (mid <= right) {
			tmpArr[third++] = data[mid++];
		}
		while (left <= center) {
			tmpArr[third++] = data[left++];
		}
		// Copy the contents of the temporary array back to the original array
		// (the contents of the original left right range are copied back to the original array)
		while (tmp <= right) {
			data[tmp] = tmpArr[tmp++];
		}
	}
 
	public static void print(int[] data) {
		for (int i = 0; i < data.length; i++) {
			System.out.print(data[i] + "\t");
		}
		System.out.println();
	}
}

Array style approach

    private static int[] mergeSort(int[] nums) {
        if (nums.length < 2) {
            return nums;
        }
        int mid = nums.length / 2;
        int[] left = Arrays.copyOfRange(nums, 0, mid);
        int[] right = Arrays.copyOfRange(nums, mid, nums.length);

        return merge(mergeSort(left), mergeSort(right));
    }

    private static int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        for (int index = 0, i = 0, j = 0; index < result.length; index++) {
            if (i >= left.length)
                result[index] = right[j++];
            else if (j >= right.length)
                result[index] = left[i++];
            else if (left[i] <= right[j])
                result[index] = left[i++];
            else
                result[index] = right[j++];
        }
        return result;
    }