Since many algorithm problems in LeetCode involve some basic data structures, in order to better understand the animation of some complex problems updated later, a new series —– “Illustrated Data Structures” is launched, mainly using animation to describe common data structures and algorithms. This series includes ten kinds, heap, queue, tree, and search set, graph and so on about dozens of articles.

You can pay attention to the public number five minutes learning algorithm for more sorting content.

Merge sort is an efficient sorting algorithm based on Merge operations. This algorithm is a very typical application of Divide and Conquer.

As a typical divide-and-conquer algorithm application, merge sort is implemented by two methods:

  • Top-down recursion (all recursive methods can be iteratively rewritten, hence the second method);
  • Bottom-up iteration;

As with select sort, merge sort performs independently of the input data, but performs much better than select sort because it is always O(nlogn) time. The trade-off is extra memory.

Algorithm steps

  1. Apply for a space equal to the sum of two sorted sequences, which is used to store the combined sequence;

  2. Set two Pointers, starting at the start of two sorted sequences;

  3. Compare the elements pointed to by the two Pointers, select the smaller element 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. Copies all remaining elements of the other sequence directly to the end of the merged sequence.

Source: github.com/hustcc/JS-S…

Algorithm demo

Sort animation process explanation

  1. First, divide the number into two regions

  2. Divide the number into two areas

  3. .

  4. Until there is only one element per region

  5. segmented

  6. Next, the segmented regions are combined

  7. When merging, the digits are moved in ascending order so that the combined digits are arranged in ascending order within the group

  8. When merging groups containing multiple numbers, compare the leading number and move the smaller number

  9. For example, in an animation, compare the beginning 4 and 3

  10. 4 is greater than 3, so we move 3

  11. Use the same logic to compare the remaining columns

  12. 4 is less than 7, so we move 4

  13. .

  14. Recursively repeats the merging operation of groups until all numbers are in one group.

  15. Merge sort done ~

Code implementation

In order to better let readers use their familiar programming language to understand animation, the author will post a variety of programming language reference code, code all from the Internet.

C++ code implementation

Java code implementation

Python code implementation

JavaScript code implementation

Github.com/MisterBooo/…
Five minutes to learn the algorithm