javascriptColumn In this article, we learn the logic behind Merge Sort and implement it in JavaScript. Finally, merge sort is compared with other algorithms in terms of space and time complexity.
Recommended (Free):JavaScript(Video)
The logic behind merge sort
Merge sort uses the concept ofdivide and conquerto sort a given list of elements. It breaks the problem into smaller sub-problems until they become simple enough to be solved directly.
Here are the steps for merge sort:
Taking the array[4, 8, 7, 2, 11, 1, 3]
as an example, let us take a look at how merge sort works:
Use JavaScript to implement merge sort
First implement a function that merges two sorted subarrays into one sorted arraymerge ()
. It is very important to note that the two subarrays are already sorted, and themerge()
function is only used for merging them.
can be achieved by traversing these two sub-arrays:
function merge(left, right) { let arr = [] // 如果任何一个数组为空,就退出循环 while (left.length && right.length) { // 从左右子数组的最小元素中选择较小的元素 if (left[0]In this function, by traversing the two sorted sub-arrays (
left
,right
) to obtain a sorted large array. First, create an empty array. Then take the smaller of the smallest elements in the two sub-arraysleft
andright
and add it to the empty array. We only need to check the first element in theleft
andright
subarrays since they are sorted.In this process, the selected element is deleted from the subarray (implemented through the
shift()
function). Continue this process until one of the subarrays becomes empty. Finally, insert the remaining elements of the non-empty subarray (because they have been sorted) into the end of the main array.Now that we have the code to merge two sorted arrays, here is the final code to implement the merge sort algorithm. This means continuing to split the array until you end up with an array containing only one element:
function mergeSort(array) { const half = array.length / 2 if(array.lengthIn the code first determine the midpoint and use the
splice()
function to split the array into two sub-arrays. array. If the number of elements is odd, the number of elements on the left will be one less. Continuously divide the array until an array of single elements is left (array.length ). Then use the previously implemented
merge()
function to merge the subarrays.After the code is implemented, test it with the previous use case:
array = [4, 8, 7, 2, 11, 1, 3]; console.log(mergeSort(array));Copy after login
The output is in line with expectations:
1,2,3,4,7,8,11
Efficiency of merge sort
The worst time complexity of merge sort is $O(n\\log n)$, which is the same as the best time complexity of quick sort. Merge sort is one of the fastest sorting algorithms currently available.
Unlike quick sort, merge sort is not anin-placesorting algorithm, which means it takes up extra space in addition to the input array. This is because we use an auxiliary array to store subarrays. The space complexity of merge sort is $O(n)$.
Another advantage of merge sort is that it is very suitable for multi-threading, because each divided half can be sorted independently. Another common way to reduce the run time of merge sort is to use insertion sort when you reach a relatively small subarray (about 7 elements). This is because insertion sort works very well with small or nearly sorted arrays.
Summary
In this article, we learned about the logic behind the Merge Sort algorithm and implemented it in JavaScript. It is one of the basic sorting algorithms and can help us better understand the divide-and-conquer strategy.
The above is the detailed content of Learn to implement merge sort with JavaScript. For more information, please follow other related articles on the PHP Chinese website!