# λ Merge sort

======= Algorithm ======= <syntax js> function mergeSort(a) { mergeSortRange(a, 0, a.length); } function mergeSortRange(a, start, end) { var len = end-start; if (len > 1) { var mid = Math.floor(len / 2 + start); // Split 'a' and merge sort a[start..mid-1] and a[mid..end-1] separately. mergeSortRange(a, start, mid); mergeSortRange(a, mid, end); // Merge the two sections of the array. var i = start, j = mid; var k = start; // Copy the front part of the array as it will be overwritten on merging. var b = a.slice(start, mid); while (i < mid || j < end) { if (i < mid && (j >= end || b[i-start] < a[j])) { a[k] = b[i-start]; i++; } else { a[k] = a[j]; j++; } k++; } } return a; } </syntax> ======= Support ======= <syntax js> function swap(a, i, j) { var t = a[i]; a[i] = a[j]; a[j] = t; } function run(a) { mergeSort(a); } </syntax> ======= Tests ======= <syntax js> </syntax> ======= Options ======= <syntax js> { "title":"Merge sort", "height":"500px" } </syntax> ======= Visualisation ======= <syntax html> <html> <head> <link rel="stylesheet" type="text/css" href="algorithms-lib/graph.css"/> <script src="http://d3js.org/d3.v2.js"></script> <script src="algorithms-lib/graph.js"></script> <script type="text/javascript"> var graph = new Graph(20); window.onload = function() { chart = graph.createGraph(d3.select("#chart")) } function args(forCloning) { return forCloning? graph.getClonableArray() : graph.array; } function update(n, x, isRunning, duration, prev) { if (duration < 0) { return; // State-less visualisation. } if (x) { graph.drawGraph(duration); drawRecursion(x); } } var stackHash = 0; function drawRecursion(x) { // Give each stack frame a hash we can key on. var mergeStack = []; for (var i=0;i<x.stack.length;i++) { if (typeof x.stack[i].lookupInScope("start") === "number") { mergeStack.push(x.stack[i]); if (!x.stack[i].hash) { x.stack[i].hash = stackHash; x.stack[i].depth = mergeStack.length-1; stackHash++; } } } // Show recursion. var recursionBars = chart.selectAll("rect.recursion").data(mergeStack, function(d) {return d.hash;}); recursionBars.enter().append("rect").classed("recursion", true); recursionBars.exit().remove(); recursionBars.attr("y", function(d) { return 256 + 5 + d.depth*4; }) .attr("height", 3) .attr("x", function(d) { return graph.barSpacing * d.lookupInScope("start"); }) .attr("width", function(d) { return graph.barSpacing * (d.lookupInScope("end")-d.lookupInScope("start")); }); } </script> </head> <body> <div style="position:absolute;padding:2px"> <button onclick="graph.randomise(200)">Random</button> <button onclick="graph.randomise(5)">Few Unique</button> <button onclick="graph.almostSorted()">Almost sorted</button> <button onclick="graph.reverse()">Reverse</button> </div> <div id="chart"></div> </body> </html> </syntax>