Merge sort algorithm is an example of divide-and-conquer algorithm.

Insertion sort, interchange sort, and selection sort all involve an unordered sequence of records arranged under a string of keywords. Merge sort is the process of combining two or more ordered sequences into one ordered sequence. Merging (merging) two ordered sequences into one is called binary merging. Merging (merging) N ordered sequences into one ordered sequence is called n-way merging.

Time complexity:

  • Time complexity: O(nlogn)
  • Space complexity: O (n)

Important note:

  • Merging is the process of merging two sorted files into a larger sorted file.
  • Merge sort is a complement to quicksort.
  • Merge sort accesses data in a sequential manner.
  • Merge sort applies to linked list sorts.
  • Merge sort is insensitive to the initial order of the input.
  • Quicksort starts with the largest child file and ends with the smallest, hence the need for a stack structure. Merge sort starts with the smallest file and ends with the largest child file, so no stack is required.
  • The merging algorithm is a stable algorithm.

Basic idea:

Merge sort is divided into two parts, split and merge. Take two-way merging as an example:

  • Divide the unordered table with length N into two unordered sub-tables in half, and continue splitting each unordered sub-table into two sub-tables in half until the length of each sub-table is 1, forming an ordered sub-table with length 1 (the ordered sub-table is the ordered sub-table when the length of the table is 1).

  • If only the last table is left, the first table will be merged with the second and the third table will be merged with the fourth table. This results in [n/2] ordered tables of length 2 (the last table may have length 1).

  • Perform the second two-way merge, and continue the two-way merge of the ordered tables obtained in the first one to get [n/4] ordered tables of length 4 (the length of the last table may be less than 4).

  • And so on, until the [logn] merge is complete, we get an ordered table of length N.

The above process can be summarized as the following idea:

Recursively split, merge two by two.

Algorithm implementation (Java) :

Public static void MergeArray(int[] A,int first,int last,int mid,int[] temp){int k=0; public static void MergeArray(int[] A,int first,int last,int mid,int[] temp); int i=first; int j=mid+1; while(i<=mid && j<=last){ if(A[i]<=A[j]){ temp[k++]=A[i++]; }else{ temp[k++]=A[j++]; } } while(i<=mid){ temp[k++]=A[i++]; } while(j<=last){ temp[k++]=A[j++]; } for(int l=0; l<k; l++){ A[first+l]=temp[l]; } } public static void MergeSort(int[] A,int first,int last,int[] temp){ int mid=(first+last)/2; // MergeSort(A, first, mid, temp); // MergeSort(A, first, mid, temp); MergeSort(A, mid+1, last, temp); MergeArray(A, first, last, mid, temp); }}Copy the code

Test procedure:

Public static void main(String[] args) {// TODO auto-generated method stub int[] A=new int[]{1,4,2,8,5,9,477,25,1}; int[] temp=new int[A.length]; long time=System.nanoTime(); MergeSort(A, 0, A.length-1, temp); System.out.println("MergeSort:"+(System.nanoTime()-time)); for (int i : A) { System.out.println(i); }}Copy the code

Print the following:

MergeSort:42863
1
1
2
4
5
8
9
25
477
Copy the code

QQ(skirt) : 985600592