Algorithms: Merge Sort

In this new series of blog posts we will discuss many kinds of algorithms. The first one is one of the fastest sorting algorithm you can find. It is called Merge Sort. As always you can find the corresponding GitHub Gist here.

Introduction

Sorting is one of the most expensive operations you can find with data structures. The easiest way of thinking about sorting are whole numbers. Imagine you have an array of integer values which were randomly added, but it is necessary to sort them in ascending order. Our goal today is to sort an array of whole numbers (e.g. [6, 3, 5, 1, 9, 4, 2, 8] -> [1, 2, 3, 4, 5, 6, 8, 9]). For simplicity reasons we will do the whole of this in JavaScript.

Disclaimer: This implementation does not tend to be the fastest, but it should be very clear how the merge sort algorithm works.

What is Merge Sort?

Merge Sort is a divide-and-conquer algorithm. A divide-and-conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem.

At first we will have to break the problem down to the smallest possible part. When using merge sort the smallest part has a length of1. Let's have a closer look at the following diagram.

The next steps are comparing, sorting and merging the two items. Now we have multiple arrays of length 2 which are sorted. Within the recursion we are going to merge all sub arrays and sort each individual new array till we have only one more array left. The final array is the ascending sorted array from the beginning.

Have a closer look at the source code.

All this is done by recursion. The merge sort algorithm has a Big O Runtime of O(n log n).

Have you ever written a sorting algorithm in your professional career? Without any doubt it is useful to know how things are working, but nowadays it is pretty uncommon to write such algorithms. Anyway, let me know about your experiences and happy coding.