javascript - Implementing merge sort iteratively -

i'm trying implement merge sort in order better understanding of how works. in following code attempting sort array of numbers. code have buggy , runs in infinite loop. i'm trying solve non-recursively now:

function mergesort(arr) {    var mid = math.floor(arr.length/2);   var left = arr.slice(0, mid);   var right = arr.slice(mid, arr.length);    if (arr.length === 1) {return arr};    var sorted = [];    var = 0;    while (left.length || right.length) {    if (left.length && right.length) {      if (left[0] < right[0]) {        sorted.push(left.shift())      } else {        sorted.push(right.shift())      }    } else if (left) {      sorted.push(left.shift())    } else {      sorted.push(right.shift())    }    i++;   }    return sorted; } 

so if have array var nums = [1, 4, 10, 2, 9, 3]; calling mergesort(nums) should return [1, 2, 3, 4, 9, 10].

you've written code splits array in 2 , merges halves. doesn't result in sorted array because 2 halves not sorted. mergesort works sorting 2 halves, merging them.

there many ways implement mergesort iteratively. let me offer one. start merging subarrays of size 1. know array of size 1 sorted, it's safe merge 2 consecutive subarrays of size 1. if consecutive pairs of subarrays of size 1 in original array, end array consisting of consecutive sorted subarrays of size 2.

do see going? can merge every 2 consecutive subarrays of size 2. end array of consecutive sorted subarrays of size 4. keep on repeating procedure until whole array sorted.

the following snippet implements approach.

function mergesort(arr) {    var sorted = arr.slice(),        n = sorted.length,        buffer = new array(n);      (var size = 1; size < n; size *= 2) {      (var leftstart = 0; leftstart < n; leftstart += 2*size) {        var left = leftstart,            right = math.min(left + size, n),            leftlimit = right,            rightlimit = math.min(right + size, n),            = left;        while (left < leftlimit && right < rightlimit) {          if (sorted[left] <= sorted[right]) {            buffer[i++] = sorted[left++];          } else {            buffer[i++] = sorted[right++];          }        }        while (left < leftlimit) {          buffer[i++] = sorted[left++];        }        while (right < rightlimit) {          buffer[i++] = sorted[right++];        }      }      var temp = sorted,          sorted = buffer,          buffer = temp;    }      return sorted;  }    function print(s) {    document.write(s + '<br />');  }    var data = [1, 4, 10, 2, 9, 3];  print('input: ' + data.join(', '));  print('output: ' + mergesort(data).join(', '));