# Bubble, Merge & Insertion sort

Let’s sort some stuff out, because sorting things is a great way to develop analytical thinking, as well as expanding your coding skills. Most of the time, you will want to use the built in methods in your language of choice, providing your own predicate (a function that returns a boolean) if needed.

But understanding how each of these approaches work can be really rewarding in terms of devising your own algorithms based on them. As a neat visual followup to this post, open this website and take a look at the pseudocode implementations and animations .

## Bubble sort

One of the first sorting techniques you will learn operates on a simple paradigm that if you compare two adjacent elements and switch their position based on their value, lower to the left, higher to the right, you will eventually, after enough iterations, end up with a sorted array. I know, this does not sound to efficient, but due to the shear simplicity of the algorithm it can still sometimes be a viable choice if you have nothing else available i guess.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
var sortIt = [5, 2, 16, 37, 12, 4, 8, 42]; function bubble(arr){ var result = Array.prototype.slice.call(arr,0), sorted = false; while(!sorted){ // set flag as true, so if no elements are out of order it will exit the while loop sorted = true; for(var i=0, l=result.length; i<l; i++){ if(result[i] > result[i+1]){ var tmp = result[i+1]; result[i+1] = result[i]; result[i] = tmp; sorted = false; } } } return result; } console.log( bubble(sortIt) ); |

Bubble sort operates in O(n^{2}) time complexity, making it a bad choice for larger arrays. Still it has O(1) space complexity so if you find the case where the application of this algorithm is the best choice, please comment 🙂

Selection sort is similar, in terms of performance and being a stable sort. Selection sort is a child’s algorithm where you simply traverse the list until you find the largest element, and append it to the sorted list. The only application of these two algorithms is when for some reason, you can not use the default library’s sorting algorithm. Even then, insertion sort is a better choice, but is slightly more difficult to implement.

## Merge sort

Merge sort has an interesting concept. By dividing the array into smaller arrays recursively, until there is only one item in the array left, we can merge the arrays while sorting them while we do it.

This approach is so popular that many js engines use it as the default sorting algorithm. Spidermonkey(Mozzilla) and JavascriptCore(Safari) use merge sort on their Array.prototype.sort() method. So let’s see how it works.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
var sortIt = [5, 2, 16, 37, 12, 4, 8, 42]; function mergeSort(arr){ if( arr.length < 2){ return arr; } var mid = parseInt(arr.length/2), left = arr.slice(0, mid), right = arr.slice(mid); // Splitting that array recursively until we get 1 item. return merge( mergeSort(left), mergeSort(right) ) } function merge(left, right){ var result = [], l = 0, r = 0; // The interesting part, where we add the items to results array in their order while(l < left.length && r<right.length){ if(left[l] < right[r]){ result.push(left[l++]); }else{ result.push(right[r++]); } } return result.concat(left.slice(l)).concat(right.slice(r)); } console.log( mergeSort(sortIt) ); |

Worst case time complexity is O(n log n) and the space complexity is always O(n). So when you need a stable O(n log n) sorting algorithm, this is about your only option. The Downside is the auxiliary space needed, but that rarely poses a problem.

## Insertion sort

Another interesting approach with two for loops. Not very “performant”, but pretty convenient in some cases. The best defense for this statement is the fact that V8 uses it to sort arrays smaller than 20 something items. A little digression here: **Performant** is a word that was made up by software developers to describe software that performs well, in whatever way you want to define performance. It is a word that is not in the dictionary yet, but I think it should be. –Stack overflow 🙂

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
var sortIt = [5, 2, 16, 37, 12, 4, 8, 42]; function insertionSort(arr){ var l = arr.length, value, i, j; for(i=0; i<l; i++){ value = arr[i]; /* the tricky part we are traversing the array from i to 0, if the current item is bigger than our current value(i) we shift the array for one place making space for our new item in the middle. */ for (j=i-1; j > -1 && arr[j] > value; j--) { arr[j+1] = arr[j]; } arr[j+1] = value; } return arr; } console.log( insertionSort(sortIt) ); |

The time complexity is O(n^{2}) and space complexity is O(1) meaning the algorithm is not very performant on large lists due to many shifting that needs to be done to insert the item on the spot. The common use case is when you have a small list, as this algorithm has a very small constant and is a stable sort.

Next, take a look at some more complex algorithms.