Merge Sorting Algorithm Recursion Summary
Tags: algorithms, tutorial, beginners, sorting
Published: 2022-02-01 23:21:18

---
title: Merge Sorting Algorithm Recursion Summary
published: true
date: 2021-07-21 00:00:00 UTC
tags: algorithm,tutorial,beginners,sorting
canonical_url: https://www.rupeshtiwari.com/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](https://codepen.io/roopkt/pen/ExWRRgP?editors=0010) for you to implement merge sort. First try by your own.
- Here is the [answer file](https://codepen.io/roopkt/pen/ZEeMPPL) for merge sort `un-optimized` version.
- Here is the [answer file](https://codepen.io/roopkt/pen/yLMQvbv?editors=0010) for merge sort space `optimized` `in-place` array sorting.

Merge sort algorithm code shared in gist also.

<script src="https://gist.github.com/85bb9242725a5a897f41522ef6744a61.js"> </script>
## Step by Step explanation for Recursive Merge Sort Algorithm

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

![](https://i.imgur.com/7297c2D.png)

![](https://i.imgur.com/JsR9WiT.png)

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

![](https://i.imgur.com/hHS3xNl.png)

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

![](https://i.imgur.com/phJfnSY.png)

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

![](https://i.imgur.com/eIa9tQY.png)

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

![](https://i.imgur.com/E4lHVoS.png)

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

![](https://i.imgur.com/BPGqO9K.png)

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

![](https://i.imgur.com/qRlvs1g.png)

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

![](https://i.imgur.com/Sac57Mq.png)

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

![](https://i.imgur.com/EDo7OuL.png)

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

![](https://i.imgur.com/IWO421x.png)

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

![](https://i.imgur.com/Et0NceF.png)

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]`.

![](https://i.imgur.com/IqzLMOY.png)

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]`.

![](https://i.imgur.com/4nkvxgp.png)

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

![](https://i.imgur.com/tgRaKe4.png)

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.

![](https://i.imgur.com/yF0Dmqm.png)

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`.

![](https://i.imgur.com/kEnaF5C.png)

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

![](https://i.imgur.com/6Bb8EZy.png)

`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.

![](https://i.imgur.com/kZ1hvzE.png)

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.

![](https://i.imgur.com/xyLPW86.png)

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]`.

![](https://i.imgur.com/bZgzA0b.png)

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.

![](https://i.imgur.com/xBTClXY.png)

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.

<script src="https://gist.github.com/1de701d2a201dda405ea701ab0030d5b.js"> </script>

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

![](https://i.imgur.com/QgcDEkf.png)

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.

![](https://imgur.com/EVK7a8N.png)

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.

![](https://i.imgur.com/HyNtQhv.png)

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.

![](https://i.imgur.com/D40d5Ti.png)

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.

![](https://i.imgur.com/5sn4Kvx.png)

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

![](https://i.imgur.com/TwgMpfB.png)

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

![](https://i.imgur.com/ju1SPTW.png)

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](https://www.fullstackmaster.net). 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](https://www.fullstackmaster.net/pro)** to access _current_ and _future_ **angular, node.js** and related courses.
- Please subscribe to **[All-Access Membership ELITE plan](https://www.fullstackmaster.net/elite)** 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](www.fullstackmaster.net) 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](https://www.fullstackmaster.net)  
Email: [rupesh.tiwari.info@gmail.com](mailto:rupesh.tiwari.info@gmail.com?subject=Hi)  
Website: [RupeshTiwari.com](https://www.rupeshtiwari.com)

![](https://imgur.com/5fBatz9.png)