Merge sort summarized by the Java sorting algorithm

This article illustrates the merge sort summary of Java sorting algorithm. Share with you for your reference. Specific analysis is as follows:

Merge, also known as a merge algorithm, is the operation of merging two sorted sequences into one sequence. Similar to quicksort, let's look at the merge implementation in Java.

Merge sort (Merge) is to Merge two (or more than two) ordered tables into a new ordered table, that is, to sort the sequence into several sub-sequences, each sub-sequence is ordered. And then merge the ordered subsequence into a whole ordered sequence.

Merge sort is an effective sorting algorithm based on merge operation. This algorithm is a very typical application of Divide and Conquer. By combining the ordered subsequences, a completely ordered sequence is obtained. That is, make each subsequence ordered first, and then make the subsequence ordered between segments. If two ordered tables are merged into one ordered table, it is called 2-way merge.

The merge sort algorithm is stable, the array needs O(n) extra space, the linked list needs O(log(n)) extra space, the time complexity is O(nlog(n)), the algorithm is not adaptive, does not need to read the data randomly.

Working principle:

1. Apply for a space whose size is the sum of two sorted sequences, and the space is used to store the merged sequences
2. Set two Pointers, the initial position of which is the starting position of two sorted sequences
3. Compare the elements pointed to by the two Pointers, select the relatively small element to put 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 merge sequence

Code implementation:

////////////////
public void mergeSort(){
 long[] workSpace = new long[nElems];
 recMergeSort(workSpace,0,nElems-1);
}
private void recMergeSort(long[] workSpace,int lowerBound,int upperBound){
 if(lowerBound == upperBound){
  return;
 }
 else{
  int mid=(lowerBound+upperBound)/2;
  recMergeSort(workSpace, lowerBound, mid);
  recMergeSort(workSpace, mid+1, upperBound);
  merge(workSpace, lowerBound, mid+1, upperBound);
 }
}
private void merge(long[] workSpace,int lowPtr,int highPtr,int upperBound){
 int j = 0;
 int lowerBound = lowPtr;
 int mid = highPtr - 1;
 int n = upperBound-lowerBound+1;
 while(lowPtr<=mid&&highPtr<=upperBound){
  if(theArray[lowPtr]<theArray[highPtr]){
  workSpace[j++]=theArray[lowPtr++];
  }
  else{
  workSpace[j++]=theArray[highPtr++];
  }
 }
 while(lowPtr<=mid){
  workSpace[j++] = theArray[lowPtr++];
 }
 while(highPtr<=upperBound){
  workSpace[j++] = theArray[highPtr++];
 }
 for(j=0;j<n;j++){
  theArray[lowerBound+j]=workSpace[j];
 }
}

Merge sort is relatively stable. That is equal to the order of the elements will not change. Such as input record 1 (1) 3 (2) (3) 2 (4) five (5) (in parentheses is the key to record words) when the output of 1 (1), 2 (3) 2 (4) 3 (2) five (5) of 2 and 2 is according to the order of the input. This to sort data contains more information and to sort based on the information of one of them, hold other information as far as possible to the input order is important. This is its advantage over quick sort.

I hope this article has been helpful to your Java programming.