merge Sort Algorithm
The Merge Sort algorithm is a highly efficient, stable, and comparison-based sorting algorithm that follows the divide and conquer paradigm. It was invented by John von Neumann in 1945 and is widely used due to its exceptional performance on large data sets and its adaptability to different data structures. The main idea behind the merge sort algorithm is to continually divide the unsorted list into smaller sublists until each sublist contains only one element, and then repeatedly merge these sublists to produce new sorted sublists until there is only one remaining sorted list.
The algorithm begins by dividing the input list into two equal halves, recursively sorting each half, and then merging the two sorted halves back together. The merging process involves comparing the first element of each sorted half and selecting the smaller one, placing it into a new sorted list. This comparison is repeated until one of the two halves has been completely merged into the new sorted list, at which point the remaining elements from the other half are simply appended to the end of the new sorted list. This process of dividing and merging continues recursively until the entire list is sorted. The merge sort algorithm has a time complexity of O(n log n), where n is the number of elements in the list, making it highly efficient and suitable for sorting large data sets.
/**
* Merge Sort is an algorithm where the main list is divided down into two half
* sized lists, which then have merge sort called on these two smaller lists
* recursively until there is only a sorted list of one.
*
* On the way up the recursive calls, the lists will be merged together inserting
* the smaller value first, creating a larger sorted list.
*/
/**
* Sort and merge two given arrays
* @param {Array} list1 - sublist to break down
* @param {Array} list2 - sublist to break down
* @return {Array} merged list
*/
function merge (list1, list2) {
var results = []
while (list1.length && list2.length) {
if (list1[0] <= list2[0]) {
results.push(list1.shift())
} else {
results.push(list2.shift())
}
}
return results.concat(list1, list2)
}
/**
* Break down the lists into smaller pieces to be merged
* @param {Array} list - list to be sorted
* @return {Array} sorted list
*/
function mergeSort (list) {
if (list.length < 2) return list
var listHalf = Math.floor(list.length / 2)
var subList1 = list.slice(0, listHalf)
var subList2 = list.slice(listHalf, list.length)
return merge(mergeSort(subList1), mergeSort(subList2))
}
// Merge Sort Example
var unsortedArray = [10, 5, 3, 8, 2, 6, 4, 7, 9, 1]
var sortedArray = mergeSort(unsortedArray)
console.log('Before:', unsortedArray, 'After:', sortedArray)
