Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

DZone's Guide to

# Friday Algorithms: JavaScript Merge Sort

· Web Dev Zone ·
Free Resource

Comment (0)

Save
{{ articles[0].views | formatCount}} Views

Learn how to add document editing and viewing to your web app on .Net (C#), Node.JS, Java, PHP, Ruby, etc.

## Merge Sort

This week I’m going to cover one very popular sorting algorithm – the merge sort. It’s very intuitive and simple as it’s described in 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 merge sort.
• Merge the two sublists back into one sorted list.

## Here’s the Source

(JavaScript)

`var a = [34, 203, 3, 746, 200, 984, 198, 764, 9]; function mergeSort(arr){    if (arr.length < 2)        return arr;     var middle = parseInt(arr.length / 2);    var left   = arr.slice(0, middle);    var right  = arr.slice(middle, arr.length);     return merge(mergeSort(left), mergeSort(right));} function merge(left, right){    var result = [];     while (left.length && right.length) {        if (left[0] <= right[0]) {            result.push(left.shift());        } else {            result.push(right.shift());        }    }     while (left.length)        result.push(left.shift());     while (right.length)        result.push(right.shift());     return result;} console.log(mergeSort(a));`

It’s interesting to see what happens in the Firebug’s console:

`[34, 203, 3, 746] [200, 984, 198, 764, 9] [34, 203] [3, 746] [34] [203] [3] [746] [200, 984] [198, 764, 9] [200] [984] [198] [764, 9] [764] [9] [3, 9, 34, 198, 200, 203, 746, 764, 984]`

Actually the tricky part in this algorithm is the merge function – it does all the work.

Extend your web service functionality with docx, xlsx and pptx editing. Check out ONLYOFFICE document editors for integration.

Topics:

Comment (0)

Save
{{ articles[0].views | formatCount}} Views

Published at DZone with permission of

Opinions expressed by DZone contributors are their own.