# Merge sorting in JavaScript

The latest addition to my [data structures and algorithms in JavaScript](https://github.com/JefClaes Data-structures-and-algorithms-in-JavaScript) is the merge sort algorithm.

There are four main steps in the merge sort algorithm (from Wikipedia):

- If the list is of length 0 or 1, then it is already sorted.

Otherwise:

- Divide the unsorted list into two sublists of about half the size.
- Sort each sublist recursively by re-applying the merge sort.
- Merge the two sublists back into one sorted list.

I found it a lot easier to understand the algorithm by just looking at this diagram (also from Wikipedia).

I added a public `mergeSort`

function to the `sortArray`

object, which I
showed in the first post in these series.

```
this.mergeSort = function() {
elements = internalMergeSort(elements, this.onSort);
return elements;
};
```

This function calls the `internalMergeSort`

function passing in the
internal elements array and the onSort callback.

```
var internalMergeSort = function(elements, onSort){
if (elements.length < 2){
return elements;
}
// Calculate the middle of the elements
var middle = Math.floor(elements.length / 2);
// Divide
var leftRange = elements.slice(0, middle);
var rightRange = elements.slice(middle, elements.length);
// Conquer
var mergingResult = merge(internalMergeSort(leftRange, onSort),
internalMergeSort(rightRange, onSort));
onSort(mergingResult);
return mergingResult;
};
```

The function recursively divides the elements in two parts, sorting them and finally merging them back together.

The `merge`

function is implemented like this.

```
function merge(left, right){
var res = [];
while (left.length > 0 && right.length > 0) {
if (left[0] <= right[0]) {
res.push(left.shift());
} else {
res.push(right.shift());
}
}
while (left.length > 0) {
res.push(left.shift());
}
while (right.length > 0) {
res.push(right.shift());
}
return res;
};
```

I peeked at this implementation, which is very similar to mine and which helped me write the first while loop more elegantly.

Testing sorting algorithms is pretty easy. So far, I have only defined one QUnit test for this algorithm.

```
test("MergeSort sorts.", function() {
var sortArray = new algorithms.sortArray();
sortArray.push(15);
...
sortArray.push(130);
var actual = sortArray.mergeSort();
var expected = [1, 10, 12, 15, 17, 22, 25, 50, 60, 90, 130];
deepEqual(actual, expected);
});
```

A small remark here is that you should use deepEqual instead of `equal`

for array assertions. We want to compare the contents of the array, not
their references.