The Merge Sort algorithm sorts an array of items in ascending order. Merge Sort is a divide-and-conquer type of algorithm. The algorithm takes n elements and recursively keeps dividing them until it reaches a state where there is only one element that it needs to focus on. Once that state is reached, it starts to combine the elements and each time it combines them, it sorts them along the way. Let’s dive into an example. We’ll start off with an array containing 8 elements.
The Merge Sort algorithm starts recursively dividing the array into n/2 sub-arrays. After the first division, the array is divided into 2 sub-arrays.
The algorithm continues to divide the sub-arrays. Both the left and right sub-arrays are divided, and the algorithm generates four new sub-arrays.
There is one final division that must be done on all four sub-arrays to create eight individual elements.
Now that the Merge Sort algorithm broke down the array into individual elements, the elements can be recombined and sorted along the way. Elements 0 and 1 will be merged, then 2 and 3, 4 and 5, and 6 and 7. We’ll create 4 placeholders to help visualize this better.
First, elements 0 and 1 are compared. Since 35 is larger than 12, element 1 is added first into the new sub-array followed by 35.
Next, the algorithm compares values at indices 2 and 3. Since 24 is less than 29, 24 is added to the new sub-array first, followed by 29.
Next, elements at indices 4 and 5 are compared. Since 1 is less than 13, 1 is added first and then 13.
Finally, values at indices 6 and 7 are compared. Since 3 is less than 45, 3 is added first to the subarray.
This completes the first merge. There are still two more to go. During the second merge, the values are compared between adjacent arrays. To start, 12 is compared with 24. There is no need to compare 12 to 35 since it’s already sorted in that list.
Since 12 was added to the list first, the left array index is incremented. The value at index 1 is compared to the value at index 2. Since 24 is less than 35, 24 is added to the list next.
The index in the second array is incremented and values 35 and 29 are compared. Since 29 is less than 35, 29 is added next. Since there are no other comparisons that 35 can be compared with, 35 is added to the list.
The Merge Sort algorithm moves to the next two sub-arrays to merge. The first indices from each subarray are compared. Since 1 is less than 3, 1 is added to the list next.
The index value in the left array is incremented and 13 is compared to 3. Since 3 is less than 13, 3 is added next to the list.
The index value of the right array is incremented and 13 is compared to 45. Since 13 is less than 45, 13 is added first and then 45. This completes the merging of four subarrays into 2 subarrays. One more merge to go.
The Merge Sort algorithm starts by comparing the first elements in each array. In this example, the value at index 0 is compared to the value at index 4. Since 1 is less than 12, 1 is added to the array first.
Since the value was added from the right array, the index value of the right array is incremented. The next comparison is between 12 and 3. Since 3 is less than 12, 3 is added to the list next.
The index value of the right array is incremented and 12 is compared to 13. Since 12 is less than 13, 12 is added to the list next.
The index value of the left array is incremented and 24 is compared to 13. Since 13 is less than 24, 13 is added to the list next.
The index value of the right array is incremented and 24 is compared to 45. Since 24 is less than 45, 24 is added to the list next.
The index value of the left array is incremented and 29 is compared to 45. Since 29 is less than 45, 29 is added to the list next.
The index value of the left array is incremented and 35 is compared to 45. Since 35 is less than 45, 35 is added next followed by 45.
The two subarrays have been merged completely and the final array is fully sorted.
