Merge Sort in Javascript Time Complexity

Question

When implementing merge sort in Javascript, lots of the code use slice to split the arrays. Wouldn't this increase the time complexity?

Does slice have a time complexity or is this ignored in the calculation?

Answer 1

Example top down merge sort. Uses a pair of mutually recursive functions (sortatob, sortatoa) to change the direction of merge based on level of recursion.

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
  }
}

---

Example bottom up merge sort. Function merge() is the same as above. Changes direction of merge on each pass by swapping references to arrays.

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 getpasscount(n)                // return # passes
{
  var i = 0
  for(var s = 1; s < n; s <<= 1)
    i += 1
  return(i)
}

function mergesort(a)
{
  var n = a.length
  if(n < 2)                             // if size < 2 return
    return
  var b = new Array(n)                  // allocate temp array
  var s = 1                             // default run size to 1
  if(0 != (1&getpasscount(n))){         //  if odd # passes swap in place
    for(var i = 1; i < n; i += 2){
      if(a[i-1] > a[i]){
        var t = a[i-1]
        a[i-1] = a[i]
        a[i] = t
      }
    }
    s = 2                               // change run size to 2
  }
  while(s < n){                         // while not done
    var ee = 0                          // reset end index
    while(ee < n){                      // merge pairs of runs
      var ll = ee                       // ll = start of left  run
      var rr = ll+s                     // rr = start of right run
      if(rr >= n){                      // if only left run
        do                              //   copy it
          b[ll] = a[ll]
        while(++ll < n)
        break                           //   end of pass
      }
      ee = rr+s                         // ee = end of right run
      if(ee > n)
        ee = n
      merge(a, b, ll, rr, ee)           // merge a[left],a[right] to b[]
    }
    var t = a                           // swap array references
    a = b
    b = t
    s <<= 1                             // double the run size
  }
}

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