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

Friday Algorithms: JavaScript Merge Sort

DZone's Guide to

Friday Algorithms: JavaScript Merge Sort

· Web Dev Zone
Free Resource

Discover how to focus on operators for Reactive Programming and how they are essential to react to data in your application.  Brought to you in partnership with Wakanda

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.

Learn how divergent branches can appear in your repository and how to better understand why they are called “branches".  Brought to you in partnership with Wakanda

Topics:

Published at DZone with permission of Stoimen Popov, DZone MVB. See the original article here.

Opinions expressed by DZone contributors are their own.

The best of DZone straight to your inbox.

SEE AN EXAMPLE
Please provide a valid email address.

Thanks for subscribing!

Awesome! Check your inbox to verify your email so you can start receiving the latest in tech news and resources.
Subscribe

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}