The Whole Merge Sort Procedure

Algorithms: Merge Sort

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 clear how the sorting algorithm works.

What is Merge Sort?

It 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 this sorting algorithm the smallest part has a length of 1. Let’s have a closer look at the following picture.

The Whole Merge Sort Procedure Merge Sort Procedure

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.

Previous Post

Leave a Comment

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.