Learn to implement merge sort with JavaScript

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 of divide and conquer to 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:

1. Split the given list in half (if the list has an odd number of elements, make them roughly equal).
2. Continue dividing the subarrays in the same way until only a single element array remains.
3. Starting from a single element array, merging subarrays so that each merged subarray is sorted.
4. Repeat step 3 until you finally get a sorted array.

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 the merge() 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] <p>In this function, by traversing the two sorted sub-arrays (<code>left</code>, <code> right</code>) to obtain a sorted large array. First, create an empty array. Then take the smaller of the smallest elements in the two sub-arrays <code>left</code> and <code>right</code> and add it to the empty array. We only need to check the first element in the <code>left</code> and <code>right</code> subarrays since they are sorted. </p><p>In this process, the selected element is deleted from the subarray (implemented through the <code>shift()</code> 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. </p><p>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: </p><pre class="brush:php;toolbar:false">function mergeSort(array) {
  const half = array.length / 2
  
  if(array.length <p>In the code first determine the midpoint and use the <code>splice()</code> 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 (<code>array.length ). Then use the previously implemented <code>merge()</code> function to merge the subarrays. </code></p><p>After the code is implemented, test it with the previous use case: </p><pre class="brush:php;toolbar:false">array = [4, 8, 7, 2, 11, 1, 3];
console.log(mergeSort(array));

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 an in-place sorting 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!