JavaScript Searching and Sorting Algorithm: Merge sort
JavaScript Searching and Sorting Algorithm: Exercise-2 with Solution
Write a JavaScript program to sort a list of elements using Merge sort.
According to Wikipedia "Merge sort (also commonly spelled mergesort) is an O (n log n) comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the implementation preserves the input order of equal elements in the sorted output."
Algorithm:
Conceptually, a merge sort works as follows :
- Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted).
- Repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist remaining. This will be the sorted list.
An example of merge sort:
Merge Sort: Pictorial Presentation
Sample Solution-1:
JavaScript Code:
function merge_sort(left_part,right_part)
{
var i = 0;
var j = 0;
var results = [];
while (i < left_part.length || j < right_part.length) {
if (i === left_part.length) {
// j is the only index left_part
results.push(right_part[j]);
j++;
}
else if (j === right_part.length || left_part[i] <= right_part[j]) {
results.push(left_part[i]);
i++;
} else {
results.push(right_part[j]);
j++;
}
}
return results;
}
console.log(merge_sort([1,3,4], [3,7,9]));
Sample Output:
[1,3,3,4,7,9]
Flowchart:
Sample Solution-2:
- Use recursion.
- Use the spread operator (...) to clone the original array, arr.
- If the length of the array is less than 2, return the cloned array.
- Use Math.floor() to calculate the index of the pivot element.
- Use Array.prototype.reduce() and Array.prototype.push() to split the array into two subarrays (elements smaller or equal to the pivot and elements greater than it), destructuring the result into two arrays.
- Recursively call quickSort() on the created subarrays.
JavaScript Code:
const quickSort = arr => {
const a = [...arr];
if (a.length < 2) return a;
const pivotIndex = Math.floor(arr.length / 2);
const pivot = a[pivotIndex];
const [lo, hi] = a.reduce(
(acc, val, i) => {
if (val < pivot || (val === pivot && i != pivotIndex)) {
acc[0].push(val);
} else if (val > pivot) {
acc[1].push(val);
}
return acc;
},
[[], []]
);
return [...quickSort(lo), pivot, ...quickSort(hi)];
};
console.log(quickSort([1, 6, 1, 5, 3, 2, 1, 4]));
Sample Output:
[1,1,1,2,3,4,5,6]
Flowchart:
Live Demo:
See the Pen searching-and-sorting-algorithm-exercise-2 by w3resource (@w3resource) on CodePen.
Improve this sample solution and post your code through Disqus
Previous: Write a JavaScript program to sort a list of elements using Quick sort.
Next: Write a JavaScript program to sort a list of elements using Heap sort.
What is the difficulty level of this exercise?
Test your Programming skills with w3resource's quiz.
JavaScript: Tips of the Day
How to insert an item into an array at a specific index (JavaScript)?
What you want is the splice function on the native array object.
arr.splice(index, 0, item); will insert item into arr at the specified index (deleting 0 items first, that is, it's just an insert). In this example we will create an array and add an element to it into index 2:
var arr = []; arr[0] = "Jani"; arr[1] = "Hege"; arr[2] = "Stale"; arr[3] = "Kai Jim"; arr[4] = "Borge"; console.log(arr.join()); arr.splice(2, 0, "Lene"); console.log(arr.join());
Ref: https://bit.ly/2BXbp04
- New Content published on w3resource:
- HTML-CSS Practical: Exercises, Practice, Solution
- Java Regular Expression: Exercises, Practice, Solution
- Scala Programming Exercises, Practice, Solution
- Python Itertools exercises
- Python Numpy exercises
- Python GeoPy Package exercises
- Python Pandas exercises
- Python nltk exercises
- Python BeautifulSoup exercises
- Form Template
- Composer - PHP Package Manager
- PHPUnit - PHP Testing
- Laravel - PHP Framework
- Angular - JavaScript Framework
- Vue - JavaScript Framework
- Jest - JavaScript Testing Framework