Объединить сортировку в javascript

Question

Я работаю через введение в алгоритмы и перевод псевдокода на различные языки для практики.

Я застрял на javascript. Я не могу понять, почему моя функция слияния не работает и дублирует входные данные. Ты знаешь почему?

Спасибо

function mergesort(a){ 
    if (a.length <=1) { 
     return a; 
     } 
    mid = Math.round((a.length/2)); 
    left = a.slice(0, mid); 
    right = a.slice(mid); 
    console.log(left,right); 
    return merge(mergesort(left), mergesort(right)); 
} 

function merge(left, right) { 
    sorted = []; 
    console.log(sorted,left, right, left[0], right[0]); 
    while (left && left.length >0 && right && right.length >0){ 
     if (left[0] <= right[0]) { 
      sorted.push(left.shift()); 
      console.log("left", left, right); 
     } 
     else { 
      sorted.push(right.shift()); 
      console.log("left", left, right); 
     } 
    } 
    return sorted.concat(left,right); 
} 


a = [234,526,6,3,2,5]; 
mergesort(a); 

Answer 1

Ваш алгоритм выглядит хорошо, большой проблема заключается в создании глобальных переменных. Когда вы создаете переменную без использования ключевого слова var, эта переменная станет глобальной переменной.

В вашем случае при первом создании глобальной переменной, а затем последовательных рекурсивных вызовах вы не создаете новые переменные, а переназначаете одни и те же глобальные переменные. Чтобы устранить эту проблему, просто префикс объявления переменных с var, как этот

var mid = Math.round((a.length/2)); 
var left = a.slice(0, mid); 
var right = a.slice(mid); 
... 
... 
... 
var sorted = []; 

С этим изменением, результат становится

[ 2, 3, 5, 6, 234, 526 ]