{"id":21,"date":"2008-02-05T17:34:12","date_gmt":"2008-02-05T23:34:12","guid":{"rendered":"http:\/\/sha.nnoncarey.com\/blog\/archives\/21"},"modified":"2012-11-16T18:12:39","modified_gmt":"2012-11-17T00:12:39","slug":"javascript-mergesort","status":"publish","type":"post","link":"https:\/\/sha.nnoncarey.com\/blog\/archives\/21","title":{"rendered":"Javascript Mergesort"},"content":{"rendered":"

A while ago, I couldn’t find any Javascript mergesort implementations, so I wrote one. The nice thing about mergesort is that it is “stable”, id est<\/em> it retains the previous order of elements with equal value. Therefore it is great for sorting rows in a table on different columns sequentially. Also, the merge() function is handy for merging two sorted arrays into one big sorted array.<\/p>\n

Check out Wikipedia<\/a> for more info on mergesort and other sorting algorithms.<\/p>\n

Here it is:<\/p>\n

\r\nvar MergeSorter = function(comparator) {\r\n\tvar merge = function(a, b)\r\n\t{\r\n\t\tvar aLen = a.length;\r\n\t\tvar bLen = b.length;\r\n\t\r\n\t\tif(aLen == 0)\r\n\t\t\treturn b;\r\n\r\n\t\tif(bLen == 0)\r\n\t\t\treturn a;\r\n\r\n\t\tvar i, j, k;\r\n\t\ti = j = k = 0;\r\n\t\tvar result = Array();\r\n\t\twhile(i < aLen && j < bLen)\r\n\t\t{\r\n\t\t\tif(comparator.compare(b&#91;j&#93;, a&#91;i&#93;))\r\n\t\t\t\tresult.push(a&#91;i++&#93;);\r\n\t\t\telse\r\n\t\t\t\tresult.push(b&#91;j++&#93;);\r\n\t\t}\r\n\t\twhile(i < aLen)\r\n\t\t\tresult.push(a&#91;i++&#93;);\r\n\t\r\n\t\twhile(j < bLen)\r\n\t\t\tresult.push(b&#91;j++&#93;);\r\n\t\r\n\t\treturn result;\r\n\t};\r\n\treturn {\r\n\t\tsort: function(a)\r\n\t\t{\r\n\t\t\tvar aLen = a.length;\r\n\t\t\tif(aLen <= 1)\r\n\t\t\t{\r\n\t\t\t\treturn a;\r\n\t\t\t} else {\r\n\t\t\t\tvar middle = Math.round(aLen \/ 2);\r\n\t\t\t\tvar left = a.slice(0, middle);\r\n\t\t\t\tvar right = a.slice(middle);\r\n\t\t\t\tleft = this.sort(left);\r\n\t\t\t\tright = this.sort(right);\r\n\t\t\t\tvar result = merge(left, right);\r\n\t\t\t\treturn result;\r\n\t\t\t}\r\n\r\n\t\t}\r\n\t}\r\n};\r\n\r\nvar normalComparator = {\r\n\tcompare: function(n1, n2)\r\n\t{\r\n\t\treturn n1 >= n2;\r\n\t}\r\n};\r\n<\/pre>\n
Here is sample code that makes use of the MergeSorter and does some sanity checks. It could easily be turned into a set of unit tests.<\/p>\n
\r\nvar mockComparator = {\r\n\t\tcalls: 0,\r\n\t\tcompare: function(n1, n2)\r\n\t\t{\r\n\t\t\tthis.calls++;\r\n\t\t\treturn n1.num &gt;= n2.num;\r\n\t\t}\r\n};\r\n\r\nfunction writeError(str)\r\n{\r\n\tdocument.write(&#39;&lt;span style=&quot;color: red;&quot;&gt;&#39; + str + &#39;&lt;\/span&gt;&lt;br&gt;&#39;);\r\n}\r\n\r\nvar size = 100000;\r\nvar ary = new Array(size);\r\nfor(var i = 0; i &lt; size; i++)\r\n{\r\n\tvar num = Math.round(Math.random() * size);\r\n\tary[i] = {num: num, id: i};\r\n}\r\ndocument.write(&#39;&lt;br&gt;&#39;);\r\n\r\nvar start = new Date().getTime();\r\nvar myMergeSorter = new MergeSorter(mockComparator);\r\nary = myMergeSorter.sort(ary);\r\nvar stop = new Date().getTime();\r\nvar executionTime = stop - start;\r\n\r\ndocument.write(&#39;Merge sorting an array with &#39; + ary.length + &#39; random integers in it...&lt;br&gt;&#39;);\r\ndocument.write(&#39;Execution time: &#39; + executionTime \/ 1000 + &#39;s&lt;br&gt;&#39;);\r\ndocument.write(&#39;Result length: &#39; + ary.length + &#39;&lt;br&gt;&#39;);\r\ndocument.write(&#39;Comparisons: &#39; + mockComparator.calls + &#39;&lt;br&gt;&#39;);\r\n\r\nvar ceilLgN = Math.ceil(Math.log(size) \/ Math.log(2));\r\nvar maxExpectedCompares = (size * ceilLgN - Math.pow(2, ceilLgN) + 1);\r\ndocument.write(&#39;Worst case (for this size): &#39; + maxExpectedCompares + &#39;&lt;br&gt;&#39;);\r\ndocument.write(&#39;Theoretical average (for this size): &#39; + (maxExpectedCompares - 0.2645 * size) + &#39;&lt;br&gt;&#39;);\r\n\r\nif(ary.length != size)\r\n{\r\n\twriteError(&#39;Result is not the right size: &#39; + ary.length);\r\n}\r\n\r\nfor(var i = 0; i &lt; ary.length; i++)\r\n{\r\n\tif(ary[i + 1])\r\n\t{\r\n\t\tif(ary[i].num &gt; ary[i + 1].num)\r\n\t\t{\r\n\t\t\twriteError(&#39;Sorting error at index &#39; + i + &#39;! &#39; + ary[i].num + &#39; greater than &#39; +\r\n\t\t\t\tary[i + 1].num);\r\n\t\t\tbreak;\r\n\t\t}\r\n\t\tif(ary[i].num == ary[i + 1].num &amp;&amp; ary[i].id &gt; ary[i + 1].id)\r\n\t\t{\r\n\t\t\twriteError(&#39;Stability error at index &#39; + i + &#39;! &#39; + ary[i].id + &#39; greater than &#39; +\r\n\t\t\t\tary[i + 1].id);\r\n\t\t\tbreak;\r\n\t\t}\r\n\t}\r\n}\r\n\r\nif(mockComparator.calls &gt; maxExpectedCompares)\r\n{\r\n\twriteError(&#39;Too many comparisons executed!&#39;);\r\n}\r\n<\/pre>\n
Edit on December 1, 2010:<\/strong> I modernized the code a bit by making use of object literals, closures, etc. The comparator no longer has to be passed down the recursion. In order to do that with merge() and sort() as top-level functions, the comparator would have to be assigned to a global variable. Also, I added a more thorough example of the usage, with sanity checks.<\/p>\n
It is worthwhile to mention that some Javascript implementations, array<\/em>.sort() is already stable. See, for example, the documentation on sort at the MDC<\/a>. Since native implementations of sort() have the potential to be much faster, it may be worthwhile to check whether this is the case and if so implement user agent testing to determine whether to use Javascript’s sort, or your own implementation.<\/p>\n","protected":false},"excerpt":{"rendered":"
A while ago, I couldn’t find any Javascript mergesort implementations, so I wrote one. The nice thing about mergesort is that it is “stable”, id est it retains the previous order of elements with equal value. Therefore it is great for sorting rows in a table on different columns sequentially. Also, the merge() function is … Continue reading “Javascript Mergesort”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[5],"tags":[],"class_list":["post-21","post","type-post","status-publish","format-standard","hentry","category-website"],"_links":{"self":[{"href":"https:\/\/sha.nnoncarey.com\/blog\/wp-json\/wp\/v2\/posts\/21","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/sha.nnoncarey.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/sha.nnoncarey.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/sha.nnoncarey.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/sha.nnoncarey.com\/blog\/wp-json\/wp\/v2\/comments?post=21"}],"version-history":[{"count":5,"href":"https:\/\/sha.nnoncarey.com\/blog\/wp-json\/wp\/v2\/posts\/21\/revisions"}],"predecessor-version":[{"id":69,"href":"https:\/\/sha.nnoncarey.com\/blog\/wp-json\/wp\/v2\/posts\/21\/revisions\/69"}],"wp:attachment":[{"href":"https:\/\/sha.nnoncarey.com\/blog\/wp-json\/wp\/v2\/media?parent=21"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/sha.nnoncarey.com\/blog\/wp-json\/wp\/v2\/categories?post=21"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/sha.nnoncarey.com\/blog\/wp-json\/wp\/v2\/tags?post=21"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}