## DEV Community is a community of 604,851 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# Sorting algorithms: JavaScript - Merge Sort π

* π€ INTRODUCTION
* ππ» ABOUT MERGE SORT ALGORITHM
* π¨π»βπ« EXPLANATION
* π VISUAL EXAMPLE
* π  IMPLEMENTATION
* π€ COMPLEXITY
* π THANK YOU

## π€ INTRODUCTION

Welcome, hackers! I hope you are all having a great weekend.πBefore we start another work week tomorrow, let's learn something new. In this blog article, we are going to explain and implement the Merge Sort algorithm.

## ππ» ABOUT MERGE SORT ALGORITHM

Merge sort algorithm is another divide-and-conquer algorithm based on the idea of breaking down a list into several sub-lists until each sublist consists of a single element and merging those sublists in a manner that results in a sorted list.

Let's take a generic array that starts at index p and going through index r. It will be convenient to have a notation for a subarray, array[p..r]; In terms of our notation, for an array of n elements, we can say that the original problem is to sort an array A[0..n-1];

## π¨π»βπ« EXPLANATION

Here is how merge sort uses divide-and-conquer:

Divide - by finding the number q of the position midway between p and r. Do this step the same way we found the midpoint in binary search: add p and r, divide by 2, and round down.

Conquer - by recursively sorting the subarray in each of the two subproblems created by the divide step. That is, recursively sort the subarray array[p..q] and recursively sort the subarray array[q+1..r];

Combine - by merging the two sorted subarrays back into the single sorted subarray array[p..r];

## π VISUAL EXAMPLE

### Steps:

0: Array [14, 7, 3, 12, 9, 11, 6, 2] is unsorted
1: Find q (q = (p+r)/2) q=3 in our case
2: We divide into two subarrays [14, 7, 3, 12] - up to the index of q - And [9, 11, 6, 2]
3: Find q again in this case for each of the subarray
The first subarray q index is 1 and for the second q=5
4: We divide into the following subarrays:
[14, 7] and [3, 12] for the first subarray and [9, 11] and
[6,2] for the second subarray.
...Repeating these steps until we have only single values as an array member. We have to make two recursive calls in the conquer step.

## π¨π»βπ» CODE

Play with the code!

## π€ COMPLEXITY

The complexity of the Merge sort algorithm is in the very best case Big O of nlog2n, in the worst case, the merge sort is staying consistent with the complexity of Big O of nlog2n.
The bad thing about the Merge sort algorithm is that requires an extra memory space the same size as the vector that is being sorted.

References:
School notes...
School books...