Merge Sorting Algorithm Recursion Summary

Learn Merge Sorting algorithm in recursion function. In this article I will show you the execution of the recursion function for Merge Sorting.

Merge sort

Merge sort is one of the most powerful sorting algorithm. Mozilla, Firefox, Chrome and many browser by default most of the time uses Merge Sort for sorting an array. You should learn Merge sort algorithm.

Complexity Analysis

• Time complexity = O(nlogn)
• Space complexity = O(n)

Merge Sort Implementation Coding

• Here is the exercise file for you to implement merge sort. First try by your own.
• Here is the answer file for merge sort un-optimized version.
• Here is the answer file for merge sort space optimized in-place array sorting.

Merge sort algorithm code shared in gist also.

Step by Step explanation for Recursive Merge Sort Algorithm

First main function will call the mergeSort with entire given array.

1st Recursion call to mergeSort with left part of the array [2,4,1,6] and pause the function execution at line number-7.

2nd recursion call with Array [2, 4] and pervious function pauses at line number -7.

3rd recursion call with array [2] and previous function pauses at line number-7

Resume 2nd recursion call with array [2,4] and call merge sort with right part [4]

3rd recursion call with array [4] and previous function pauses at line number -8.

This function will exit since length is less than 2. Therefore, 3rd recursion call resumes and executes at line number-9.

Which is a call to stitch method which will join both left and right array and re-order them in ascending order.

Resume 2nd recursion method at line number-7 and call mergeSort with right part of the array [1,6].

Pause the function at line numnber-7 and call mergeSort with [1] which will exit because of base condition.

Function resume at line numnber-7 and execute line number-8 call mergeSort with [6]

Next mergeSort with [6] will exit because of base condition. Next function will resume at line number-9 and stitch method will call that will re-order array [1,6].

Next Resume 1st recursion at line number-7 and execute mergeSort with [8,5,3,7]. Next function will pause at line number-7 and will call mergeSort recursively with [8,5].

Next first it will make mergeSort with [8] and pause at line number-7.

Next It will pause the previous function at line number-7. And Resume at line number-8 and call mergeSort recursively with [5] and pause again at line number-8, which will exit.

Therefore, function will resume at line number-8 and execute stitch to sort the array. Hence the array will become [5,8] and exit the function. The previous function resumes at line number-7 and call mergeSort recursively with [3,7] and pauses at line number-9.

Next, it will call mergeSort with [3] recursively then pause at line number-7.

mergeSort with [3] will exit and then previous function will resume again at number-7 and execute next line which will call mergeSort with [7] recursively then pauses at line number-8. mergeSort with [7] exit function.

And then previous function will resume again at number-8 and execute next line stitch function that will sort the array in ascending order to [3,7] and exit.

Next 1st iteration function will resume at line number-9 and stitch the array [5,8] and [3,7] and reorder the array A to [3,5,7,8].

Finally, the 1st function will resume at line number-8 and call stitch method to re-order the array [1,2,3,4,5,6,7,8] and finally exit. This way you get the sorted array.

Sorting is done! however let me explain you the stitch algorithm which is the core part or merge sort.

Merge sort Stitch algorithm

You might have noticed that MergeSort Method is calling stitch at every recursion method. Now I will explain the stitch function to you. This is the algorithm that takes left, right and original array. Then it will re-order the original array in ascending order.

Here is the stitch algorithm code used for merge sort.

First compare left with right array 1st element. 1 is less than 3 so copy 1 at A[0].

Next compare 2 in left array with 3 in Right array. Since 2 is less than 3. Copy 2 at A[1]. Increment left and A array indices.

Next compare 4 in left array with 3 in right array and since 4 is more than 3. Copy 4 to A[2] and increment A and R array indices.

Next compare 4 in left array with 5 in Right array. Since 4 is less than 5. Copy 4 at A[3]. Increment left and A array indices.

Next compare 6 in left array with 5 in right array and since 6 is more than 5. Copy 5 to A[4] and increment A and R array indices.

Next iterate over left array and copy remaining elements at Array A and increment both indices.

Finally, iterate over right array and copy remaining elements at Array A and increment both indices.

I hope you have enjoyed this visual walkthrough of Merge sort algorithm.

---

Thanks for reading my article till end. I hope you learned something special today. If you enjoyed this article then please share to your friends and if you have suggestions or thoughts to share with me then please write in the comment box.

Become full stack developer 💻

I teach at Fullstack Master. If you want to become Software Developer and grow your carrier as new Software Engineer or Lead Developer/Architect. Consider subscribing to our full stack development training programs. You will learn Angular, RxJS, JavaScript, System Architecture and much more with lots of hands on coding. We have All-Access Monthly membership plans and you will get unlimited access to all of our video courses, slides, download source code & Monthly video calls.

• Please subscribe to All-Access Membership PRO plan to access current and future angular, node.js and related courses.
• Please subscribe to All-Access Membership ELITE plan to get everything from PRO plan. Additionally, you will get access to a monthly live Q&A video call with Rupesh and you can ask doubts/questions and get more help, tips and tricks.

Your bright future is awaiting for you so visit today FullstackMaster and allow me to help you to board on your dream software company as a new Software Developer, Architect or Lead Engineer role.

💖 Say 👋 to me!
Rupesh Tiwari
Founder of Fullstack Master
Email: rupesh.tiwari.info@gmail.com
Website: RupeshTiwari.com