What is merge sort? Detailed explanation of merge sort in Java

Java implementation of merge sort

Merge sort (MERGE-SORT) is an effective sorting algorithm based on the merge operation. This algorithm is a very typical use of the divide and conquer method (pide and Conquer). Applications. Merge the already ordered subsequences to obtain a completely ordered sequence; that is, first make each subsequence orderly, and then make the subsequence segments orderly. If two ordered lists are merged into one ordered list, it is called a two-way merge. The merging process is: compare the sizes of a[i] and b[j], if a[i]≤b[j], copy the element a[i] in the first ordered list to r[k] , and add 1 to i and k respectively; otherwise, copy the element b[j] in the second ordered list to r[k], and add 1 to j and k respectively, and so on, until After one ordered list is fetched, the remaining elements in the other ordered list are copied to the cells in r from subscript k to subscript t. We usually use recursion to implement the merge sorting algorithm. We first divide the interval to be sorted [s, t] into two at the midpoint, then sort the left sub-range, then sort the right sub-range, and finally use a merge operation between the left interval and the right interval. Merge into ordered intervals [s,t].

Two main points:

1How to merge two ordered sequence into one ordered sequence

2How to turn these two sequence into an ordered sequence

Solve the first problem:

How to merge two ordered sequences. This is very simple. Just compare the first number of the two sequence and take the smaller one first. After taking it, delete the number in the corresponding sequence. Then compare them. If one of the columns is empty, just take out the data of the other column one by one.

public static void merge(int[] nums, int low, int mid, int high) {  
        int[] temp = new int[high - low + 1];  
        int i = low;// 左指针  
        int j = mid + 1;// 右指针  
        int k = 0;  
  
        // 把较小的数先移到新数组中  
        while (i <= mid && j <= high) {  
            if (nums[i] < nums[j]) {  
                temp[k++] = nums[i++];  
            } else {  
                temp[k++] = nums[j++];  
            }  
        }  
  
        // 把左边剩余的数移入数组  
        while (i <= mid) {  
            temp[k++] = nums[i++];  
        }  
  
        // 把右边边剩余的数移入数组  
        while (j <= high) {  
            temp[k++] = nums[j++];  
        }  
  
        // 把新数组中的数覆盖nums数组  
        for (int k2 = 0; k2 < temp.length; k2++) {  
            nums[k2 + low] = temp[k2];  
        }  
    }

The second question: Groups A and B can be divided into two groups. By analogy, when the separated group has only one data, it can be considered that the group has reached order, and then the two adjacent groups can be merged. In this way, merge sorting is completed by first recursively decomposing the array and then merging the array.

public static int[] sort(int[] nums, int low, int high) {  
        int mid = (low + high) / 2;  
        if (low < high) {  
            // 左边  
            sort(nums, low, mid);  
            // 右边  
            sort(nums, mid + 1, high);  
            // 左右归并  
            merge(nums, low, mid, high);  
        }  
        return nums;  
    }

Full code:

package algorithm;import java.util.Arrays;public class MergeSort {	  public static int[] sort(int[] nums, int low, int high) {  
	        int mid = (low + high) / 2;  
	        if (low < high) {  
	              
	            sort(nums, low, mid);  
	             
	            sort(nums, mid + 1, high);  
	             
	            merge(nums, low, mid, high);  
	        }  
	        return nums;  
	    }  
	  
	    public static void merge(int[] nums, int low, int mid, int high) {  
	        int[] temp = new int[high - low + 1];  
	        int i = low;	        int j = mid + 1;  
	        int k = 0;  
	  
	        while (i <= mid && j <= high) {  
	            if (nums[i] < nums[j]) {  
	                temp[k++] = nums[i++];  
	            } else {  
	                temp[k++] = nums[j++];  
	            }  
	        }  
	  
	      
	        while (i <= mid) {  
	            temp[k++] = nums[i++];  
	        }  
	  
	      
	        while (j <= high) {  
	            temp[k++] = nums[j++];  
	        }  
	  
	        
	        for (int k2 = 0; k2 < temp.length; k2++) {  
	            nums[k2 + low] = temp[k2];  
	        }  
	    }  
	public static void main(String[] args) {		  int[] nums = { 29, 78, 800, 3, 551, 6, 97, 0, 5, 4 };  
		  
	        MergeSort.sort(nums, 0, nums.length-1);  
	        System.out.println(Arrays.toString(nums));  
	}

}

The above is the detailed content of What is merge sort? Detailed explanation of merge sort in Java. For more information, please follow other related articles on the PHP Chinese website!