Created
August 18, 2015 10:34
-
-
Save OzTamir/0937c38e41fb6b06702a to your computer and use it in GitHub Desktop.
Merge sort example in JS
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| <!DOCTYPE html> | |
| <html> | |
| <head> | |
| <script src="merge_sort.js"></script> | |
| <title>Merge Sort</title> | |
| </head> | |
| <body> | |
| <h1>Merge Sort!</h1> | |
| <span> | |
| Array: <p id="arrayText">[7, 4, 2, 3, 8, 6, 1, 5, -1, 100]</p> | |
| </span> | |
| <input id="sortThingsOut" type="button" value="SORT" onclick="main();"/> | |
| </body> | |
| </html> |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| //--------------- | |
| // Merge sort example in JS | |
| // Written by Oz Tamir | |
| // 18/08/2015 | |
| //--------------- | |
| merge = function(arr1, arr2) { | |
| // * Merge two arrays into one sorted array * // | |
| var res = []; | |
| // Do the initial merge until one array is out of items | |
| while (arr1.length > 0 && arr2.length > 0) { | |
| if (arr1[0] < arr2[0]) { | |
| res.push(arr1[0]); | |
| arr1.splice(0, 1); | |
| } | |
| else { | |
| res.push(arr2[0]); | |
| arr2.splice(0, 1); | |
| }; | |
| }; | |
| // Than add the remaining items from the other array | |
| if (arr1.length == 0) { | |
| res = res.concat(arr2); | |
| } | |
| else { | |
| res = res.concat(arr1); | |
| }; | |
| return res | |
| } | |
| merge_sort = function(arr) { | |
| // * Sort an array using recursive merge sort * // | |
| // Breaking condition | |
| if (arr.length <= 1) return arr; | |
| // Split the array into two parts | |
| var first_half = arr.slice(0, Math.ceil(arr.length / 2)); | |
| var second_half = arr.slice(Math.ceil(arr.length / 2) , arr.length); | |
| // Do the magic trick | |
| return merge(merge_sort(first_half), merge_sort(second_half)); | |
| } | |
| main = function() { | |
| var example_array = [7, 4, 2, 3, 8, 6, 1, 5, -1, 100]; | |
| var sorted_array = merge_sort(example_array); | |
| document.getElementById("arrayText").innerHTML = ["[", sorted_array.toString(), "]"].join(""); | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment