Merge sort is a sorting algorithm that uses the “divide and conquer” concept.

Given an array, we first divide it in the middle and we get 2 arrays.

We recursively perform this operation, until we get to arrays of 1 element.

Then we start building up the sorted array from scratch, by ordering the individual items we got.

Suppose our array is this:

[4, 3, 1, 2]


We first divide the array into 2 arrays:

[4, 3]
[1, 2]


then we recursively divide those arrays:

[4]
[3]


and

[1]
[2]


Then it’s time to construct the result, by ordering those pairs of elements first:

[3, 4]
[1, 2]


Then we merge those 2 arrays:

[1, 2, 3, 4]


Let’s do another example with more items in the array, this time using letters:

['e', 'g', 'a', 'd', 'f', 'c', 'b']


We divide the array in 2:

['e', 'g', 'a']
['d', 'f', 'c', 'b']


Then we divide the first array in 2:

['e']
['g', 'a']


and we divide the second result:

['g']
['a']


We now take the second part of the original array and we divide it in 2:

['d', 'f']
['c', 'b']


We divide both items:

['d']
['f']

['c']
['b']


Now we have a list of 1-item arrays:

['e']
['g']
['a']
['d']
['f']
['c']
['b']


Now we order them in pairs:

['e', 'g']
['a', 'd']
['d', 'f']
['c', 'b']


Then we order the first 2 arrays and the last 2:

['a', 'd', 'e', 'g']
['c', 'b', 'd', 'f']


Finally we merge the 2 arrays we got:

['a', 'b', 'c', 'd', 'e', 'f', 'g']


We can implement this algorithm using 2 functions. The first called mergeSort, which is the function we’ll call, and another one called _mergeArrays, which takes care of merging the arrays. I prepended _ to its name, to signal it’s not meant to be called directly.

Here they are:

const _mergeArrays = (a, b) => {
const c = []

while (a.length && b.length) {
c.push(a[0] > b[0] ? b.shift() : a.shift())
}

//if we still have values, let's add them at the end of c
while (a.length) {
c.push(a.shift())
}
while (b.length) {
c.push(b.shift())
}

return c
}

const mergeSort = (a) => {
if (a.length < 2) return a
const middle = Math.floor(a.length / 2)
const a_l = a.slice(0, middle)
const a_r = a.slice(middle, a.length)
const sorted_l = mergeSort(a_l)
const sorted_r = mergeSort(a_r)
return _mergeArrays(sorted_l, sorted_r)
}


Notice how in _mergeArrays() we initialize a resulting array c that we fill with the values of the 2 arrays a and b we pass to the function, ordered by value. Calling shift() on an array will remove the first item in the array, returning it, so we pass it to c.push() to add it to the c array.

The complexity of this algorithm is O(n log(n)), which makes it very efficient.

## One more thing! ⚠️ ✋

At the end of January I will organize the Web Development Bootcamp.

It's a 10-weeks long cohort online course where I will guide you to becoming a Web Developer.

It's not "just a course". It's a big event I organize once a year.

We'll start from zero, learn the fundamentals of Web Development, HTML CSS, JavaScript, Tailwind, Git, using the command line, VS Code, GitHub, Node.js, we'll then learn React, JSX, how to use PostgreSQL, Astro, Next.js, Prisma, deploying on Netlify/DigitalOcean/Fly/Vercel and much more!

At the end of the first 10 weeks you'll know how to create web sites and web applications and I'll unlock you the 2nd phase of the Bootcamp: you will get access to a large number of projects exclusive to the Bootcamp graduates, so you can follow my instructions to build things like private areas with authentication, clones of popular sites like Twitter YouTube Reddit, create e-commerce sites, and much much more.

Because once you got the fundamentals, you only learn by working on real, exciting projects.

To find out more, visit bootcamp.dev