preface
The concept is introduced
- Merge sort algorithm is an effective sort algorithm for remerge operation.
- This algorithm is a very typical application of divide and conquer
- Two ways to implement merge sort
- Recursion from the top down
- Bottom-up iteration
The principle of interpretation
Take [11 41 45 42 36 27 40 4] as an example to illustrate the realization principle of merge sort algorithm
- The traversal has not started, and the effect is shown below
- The 8 elements of this sequence are artificially regarded as 8 sub-sequences [11],[41],[45],[42],[36],[27],[4] of the sequence [11 41 45 42 36 27 40 4]. The effect is shown in the figure below
- Four new sub-sequences [11 41],[42 45],[27 36],[4 40] are obtained by merging the above eight sub-sequences in pairs (the element with the small value is first, and the element with the large value is last), and the effect is shown in the figure below
- Two new subsequences [11 41 42 45] and [4 27 36 40] are obtained by merging the above four subsequences in pairs (the element with the small value is first and the element with the large value is last). The effect is shown in the figure below
- A new sequence [11 41 42 45],[4 27 36 40] is obtained by merging the above two subsequences in pairs (the element with the small value is in the first place, and the element with the large value is in the second). The effect is shown in the figure below
- At this point, the whole merge sort process is finished. Overall effect below
Time complexity
- It can be seen from the realization process of merging algorithm that the time complexity of each merging operation is O(N), and the depth of binary tree is log2^N
- So the total time of merge is order N log base 2 to the N.
Spatial complexity
- The space occupied by temporary array data n, the space occupied by data pushed recursively logn;
- Therefore, the total space complexity of merging algorithm is O(n).
Advantages and disadvantages of the algorithm
- Advantages: High efficiency, reached the peak of efficiency based on comparison sorting; Algorithm is stable
- Disadvantages: High space complexity
Results show
Download the source code
- Please reply “algorithm source code” in the public number to get the top ten classic sorting algorithm source code
For more algorithm learning, please pay attention to my public number
