Merge sort implementation JavaScript-CodePudding

I was trying to implement merge sort algorithm in JavaScript without built in methods like slice(), splice(), etc. It doesn’t work exactly I wish. Can you help me to figure out where is bug hidden? Getting output [3, 5, 5, 3, 7] instead of [3, 5, 5, 7, 8].

// Merge Sort implementation

// sort implementation
function sort(arr, start, mid, end) {

  // Creation and filling the temp arrays
  let lArray = [];
  let rArray = [];

  for (let i = 0; i <= mid - start; i  ) {
    lArray[i] = arr[start   i];
  }

  for (let j = 0; j <= end - mid - 1; j  ) {
    rArray[j] = arr[mid   1   j];
  }


  // Sorting and updating current array
  let i = 0;
  let j = 0;
  let k = start;

  while (i < lArray.length && j < rArray.length) {
    if (lArray[i] < rArray[j]) {
      arr[k] = lArray[i];
      i  ;
      k  ;
    } else {
      arr[k] = rArray[j];
      j  ;
      k  ;
    }
  }

  // Handling last element in lArray or rArray

  i < lArray.length ? arr[k] = lArray[i] : arr[k] = rArray[j];
}

// Recursive Merge Sort 
function recursiveMergeSort(arr, start, end) {
  if (start < end) {
    let mid = Math.floor(((end)   start) / 2);
    //console.log(start, end, mid);
    recursiveMergeSort(arr, start, mid);
    recursiveMergeSort(arr, mid   1, end);
    sort(arr, start, mid, end);
  }
}

function mergeSort(arr) {

  let start = 0;
  let end = arr.length - 1;

  recursiveMergeSort(arr, start, end);
  return (arr)
}

console.log(mergeSort([5, 8, 3, 7, 5]));

CodePudding user response：

// Handling last element in lArray or rArray is not correct.

After merging arrays you have to check the rests and copy untreated tail if it does exist

 while (i < lArray.length) {
     arr[k] = lArray[i];
     i  ;
     k  ;
 }
 while (j < rArray.length) {
     arr[k] = rArray[j];
     j  ;
     k  ;
 }

Replacing ternary operator by this code gives correct results for given data

CodePudding user response：

Example of a somewhat optimized version of top down merge sort. It does a one time allocation of a working array and uses a pair of mutually recursive functions to change the direction of merge for each level of recursion. Takes about 1/4 second to sort 1 million pseudo-random integers on my system:

// merge sort top down

function merge(a, b, bgn, mid, end) {
  var i = bgn                           // left:  a[bgn,mid)
  var j = mid                           // right: a[mid,end)
  var k = bgn                           // index for b[]
  while(true){
    if(a[i] <= a[j]){                   // if left <= right
      b[k  ] = a[i  ]                   //   copy left
      if(i < mid)                       //   if not end of left
        continue                        //     continue back to while
      do                                //   else copy rest of right
        b[k  ] = a[j  ]
      while(j < end)
      break                             //     and break
    } else {                            // else left > right
      b[k  ] = a[j  ]                   //   copy right
      if(j < end)                       //   if not end of right
        continue                        //     continue back to while
      do                                //   else copy rest of left
        b[k  ] = a[i  ]
      while(i < mid)
      break                             //     and break
    }
  }
}

function sortatob(a, b, bgn, end) {     // sort a to b
  if ((end-bgn) < 2){
    b[bgn] = a[bgn]
    return
  }
  var mid = Math.floor(bgn   (end - bgn) / 2)
  sortatoa(a, b, bgn, mid)
  sortatoa(a, b, mid, end)
  merge(a, b, bgn, mid, end)
}

function sortatoa(a, b, bgn, end) {     // sort a to a
  if ((end-bgn) < 2)
    return
  var mid = Math.floor(bgn   (end - bgn) / 2)
  sortatob(a, b, bgn, mid)
  sortatob(a, b, mid, end)
  merge(b, a, bgn, mid, end)
}

function mergesort(a) {                 // entry function
  if(a.length < 2)
      return
  var b = new Array(a.length)           // allocate temp array
  sortatoa(a, b, 0, a.length)           // start with sort a to a
}

var a = new Array(1000000)
for (i = 0; i < a.length; i  ) {
  a[i] = parseInt(Math.random() * 1000000000)
}
console.time('measure')
mergesort(a)
console.timeEnd('measure')
for (i = 1; i < a.length; i  ) {
  if(a[i-1] > a[i]){
    console.log('error')
    break
  }
}