Detailed explanation of method examples for implementing merge sort algorithm in Java

This article mainly introduces relevant information about the detailed explanation of the merge sort algorithm in Java. The merge sort algorithm is also called the merge sort algorithm. It is a sorting algorithm with a time complexity of O(N logN), so it is used in daily life. It is widely used in work. Friends who need it can refer to the detailed explanation of the merge sort algorithm in

The merge sort algorithm, as the name suggests, is a method that divides first and then combines Algorithm, the algorithm idea is to decompose the array to be sorted into individual elements, each element is a single individual, and then sort the two adjacent elements from small to large or from large to small to form a whole. Each whole contains one or two elements, and then continue to "merge" adjacent wholes. Because each whole is sorted, a certain algorithm can be used to merge them. After merging, each whole contains three elements. After reaching four elements, continue to merge adjacent wholes until all the wholes are merged into one whole. The final whole is the result of sorting the original array.

For adjacent wholes, the idea of ​​​​merging is to take the smallest element of the two wholes (assuming they are actually sorted in ascending order) and put it into a new array each time, and then cycle through it. Finally, the two wholes After all the elements in are taken, a whole sorted in ascending order will be obtained. The merging process is like having two ascending-ordered decks A and B (as shown in the figure). Each time one element is taken from the top and placed into deck C:

It can be seen from the picture that for two adjacent wholes A and B, the elements inside are sorted in ascending order. Now there is a temporary array C, and then the two elements at the top of A and B are sorted Compare, take out the smaller element and put it into C. For the whole taken out element, the subscript pointing to the element is moved down one place. Continue to take out the smaller one of the top elements of the two wholes and put it into C, and loop in sequence. , when the elements of a certain whole are fetched, all the elements of the other whole are directly moved into C. For the whole C, it is obtained by sorting A and B. Since A and B are two adjacent wholes, in the end, you only need to copy the elements in C to a common whole composed of A and B. That is However, this also achieves the purpose of merging A and B and sorting them at the same time.

The following is the specific algorithm of merge sort:

public class MergeSort {
 public static <AnyType extends Comparable<? super AnyType>> void mergeSort(AnyType[] arr) {
  AnyType[] tmp = ((AnyType[]) new Comparable[arr.length]);
  mergeSort(arr, 0, arr.length - 1, tmp);
 }

 private static <AnyType extends Comparable<? super AnyType>> void mergeSort(AnyType[] arr, int start, int end, AnyType[] tmp) {
  if (start < end) {
   int mid = (start + end) >> 1;
   mergeSort(arr, start, mid, tmp);
   mergeSort(arr, mid + 1, end, tmp);
   merge(arr, start, mid, end, tmp);
  }
 }

 private static <AnyType extends Comparable<? super AnyType>> void merge(AnyType[] arr, int start, int mid, int end, AnyType[] tmp) {
  int i = start, j = mid + 1, k = start;
  while (i <= mid && j <= end) {
   if (arr[i].compareTo(arr[j]) < 0) {
    tmp[k++] = arr[i++];
   } else {
    tmp[k++] = arr[j++];
   }
  }

  while (i <= mid) {
   tmp[k++] = arr[i++];
  }

  while (j <= end) {
   tmp[k++] = arr[j++];
  }

  for (int m = start; m <= end; m++) {
   arr[m] = tmp[m];
  }
 }
}

There are two main methods in the code

private static <AnyType extends Comparable<? super AnyType>> void mergeSort(AnyType[] arr, int start, int end, AnyType[] tmp)

private static <AnyType extends Comparable<? super AnyType>> void merge(AnyType[] arr, int start, int mid, int end, AnyType[] tmp)

The first method is a recursive method. For the recursive method, the function of the method must be clearly defined. The purpose of the recursive method here is to pass The elements between start and end of the input array are sorted, and tmp is an auxiliary array. In the specific implementation of this method, we can see that the idea is to first continue to call recursion to sort the elements between start and mid, and then call recursion to sort the elements between mid to end. After these two method, the elements from start to mid and from mid to end are sorted, and the second method needs to be called at this time.

The function of the second method is to merge the two sorted parts

. For the first method, the last step executes the second method, which is to sort the previous two steps. After merging the parts, the function of this method is completed. For the second method, the implementation idea is the same as described before. Take the smaller element from the top of the two piles of cards and put it into a temporary array. When one pile of cards is taken out, put the remaining elements of the array into The second deck, finally puts the elements of the temporary array back into the original array. This article mainly explains the idea of ​​merge sort in detail, and analyzes the code based on specific code and ideas.

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