How does merge sort decide how to merge an array?

So, the way I understand merge sort: We split an array into two halves, then we split those halves into halves, etc. until we get arrays that can be split no further. We kind of build up a tree in the process. Then we do what I call "compare, sort, merge." Starting with the unit-length arrays, we compare the first element of each sibling array. If the first element of array A is greater than (or less than, depending on which order is wanted) the first element of array B, then the values are swapped out. The arrays are then merged as follows:

[element 0, array A, element 0 array B, element 1 array A, element 1 array B]

For example, given the array [14,34,9,20], the arrays are split 2 times: first into [14,34], then into [14],[34],[[9],[20]. Since 14<34, nothing happens. Since 9<20, nothing happens there. So we end up with [14,34],[9,20]. Since 14 > 9, we end up with [9,34],[14,20]. 34>20, so we end up with [9,20],[14,34]. Then we merge the arrays without comparing values - the first elements of each array go first, followed by the second elements of each array, like so: [9,14,20,34].

Am I understanding correctly?

• We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. You should be able to execute pseudocode by hand to see if your reasoning is correct.
– D.W.
Jun 12, 2023 at 19:20
• "If the first element of array A is greater than (or less than, depending on which order is wanted) the first element of array B, then the values are swapped out." - no Jun 12, 2023 at 21:03

I am not sure what you want to be confirmed in your explanation. The structure of MergeSort is a typical Divide & Conquer pattern as follows:

MergeSort(S):
if |S| == 1
Skip; // Nothing to do, S is already sorted
else
S0, S1:= Split(S); // S0 and S1 are two halves of S
MergeSort(S0); MergeSort(S1); // Now, S0 and S1 are sorted (by recursion)
S:= Merge(S0, S1); // Now S is sorted


The Split operation is trivial. The Merge is the interesting operation. It relies on the fact that you can obtain a single sorted sequence from two independent sorted sequences in a single pass, by intertwining the elements in increasing order.

MergeSort(14, 34, 20, 9)
MergeSort(14, 34)
MergeSort(14) -> 14
MergeSort(34) -> 34
Merge(14; 34) -> 14, 34
MergeSort(20, 9)
MergeSort(20) -> 20
MergeSort(9) -> 9
Merge(20; 9) -> 9, 20
Merge(14, 34; 9, 20) -> 9, 14, 20, 34


MergeSort has many good properties. Unfortunately, the Merge step cannot be performed in-place, so extra space is required on every recursion level.

• In fact the merge can be done in-place but with a complicated procedure, which is never used.
– user16034
Jun 13, 2023 at 7:03