Detailed explanation of merge sort in JavaScript

This article talks about merge sorting in JavaScript. If you don’t know about merge sorting in JavaScript or are interested in merge sorting in JavaScript, then let’s take a look at this article. Okay, without further ado, let’s get to the point. Bar

Merge sort in JavaScript

#As a typical algorithm application of divide and conquer thinking, the implementation of merge sort consists of two Method:

1. Top-down recursion (all recursive methods can be rewritten using iteration, so there is the second method)

2. Bottom-up iteration

In "Data Structure and Algorithm JavaScript Description", the author gives a bottom-up iteration method. But regarding the recursive method, the author thinks:

However, it is not possible to do so in JavaScript, as the recursion goes too deep for the language to handle.
然而,在 JavaScript 中这种方式不太可行,因为这个算法的递归深度对它来讲太深了。

To be honest, I don’t quite understand this sentence. Does it mean that the memory of the JavaScript compiler is too small and recursion is too deep, which can easily cause memory overflow? I hope someone can give me some advice.

Like selection sort, the performance of merge sort is not affected by the input data, but the performance is much better than selection sort, because the time complexity is always O(n log n). The price is additional memory space.

Merge sort animation demonstration

Merge sort JavaScript code implementation:

function mergeSort(arr) {  //采用自上而下的递归方法  
   var len = arr.length;  
   if(len < 2) {  
       return arr;  
   }  
   var middle = Math.floor(len / 2),  
       left = arr.slice(0, middle),  
       right = arr.slice(middle);  
   return merge(mergeSort(left), mergeSort(right));}function merge(left, right){  
   var result = [];  
  
   while (left.length && right.length) {  
       if (left[0] <= right[0]) {  
           result.push(left.shift());  
       } else {  
           result.push(right.shift());  
       }  
   }  
  
   while (left.length)  
       result.push(left.shift());  
  
   while (right.length)  
       result.push(right.shift());  
  
   return result;}

The above is all the content of this article, if you If you don’t know much about it yet, you can easily master it if you can implement both sides yourself!

Related recommendations:

JavaScript Interesting Question: Merge Sorting of Linked Lists

JavaScript implements linked list insertion sorting and Linked list merge sort

The above is the detailed content of Detailed explanation of merge sort in JavaScript. For more information, please follow other related articles on the PHP Chinese website!