面试题：合并两个有序数组为一个有序数组

试题：给定两个有序数组 [1, 2, 4, 9, 10, 15, 33] 和 [3, 5, 8, 9, 13]，合并为一个有序数组

思路一：

var a = [1, 2, 4, 9, 10, 15, 33]
var b = [3, 5, 8, 9, 13]

merge(a, b)

function merge(a, b) {
    var ret = []

    if (a[0] > b[0]) {
        ret = ret.concat(find(a, b))
    } else {
        ret = ret.concat(find(b, a))
    }

    return ret
}

// 假设 a[0] > b[0]
function find(a, b) {
    var ret = []
    var ia = 0
    var ib = 0

    // 探寻本次ib End
    while (a[ia] >= b[ib]) {
        ib++
    }

    // 探寻本次ia End
    ia++
    while (a[ia] >= b[ib - 1] && a[ia] < b[ib]) {
        ia++
    }

    ret = ret.concat(b.slice(0, ib), a.slice(0, ia))

    if (ia === a.length) {
        return ret.concat(b.slice(ib, b.length))
    } else if (ib === b.length) {
        return ret.concat(a.slice(ia, a.length))
    } else {
        return ret.concat(merge(a.slice(ia), b.slice(ib)))
    }
}

思路二：

var a = [1, 2, 4, 9, 10, 15, 33]
var b = [3, 5, 8, 9, 13]

var c = merge(a, b)
console.log(c.join())

// 假设 a[0] < b[0]
function merge(a, b) {
  var splitPoint = []
  var ret = []
  var i = 0
  var splitIndex = 0
  var len, x, y, splitNumber, start, end

  if (a[0] < b[0]) {
    x = a
    y = b
  } else {
    x = b
    y = a
  }

  splitNumber = y[0]
  while (splitIndex !== x.length && splitIndex !== y.length) {
    if (i++ % 2) {
      splitIndex = binaryInsertion(y, splitNumber)
      splitNumber = y[splitIndex]
    } else {
      splitIndex = binaryInsertion(x, splitNumber)
      splitNumber = x[splitIndex]
    }
    splitPoint.push(splitIndex)
  }

  if (splitIndex === x.length) {
    splitPoint.push(x.length, y.length)
  } else if (splitIndex === y.length) {
    splitPoint.push(y.length, x.length)
  }

  splitPoint.unshift(0, 0)
  for (i = 2, len = splitPoint.length; i < len; i++) {
    start = splitPoint[i - 2]
    end = splitPoint[i]
    if (i % 2) {
      ret = ret.concat(y.slice(start, end))
    } else {
      ret = ret.concat(x.slice(start, end))
    }
  }
  return ret
}

function binaryInsertion(arr, find) {
  if (arr.length === 1) {
    return arr[0] <= find ? 1 : 0
  }

  var mid = Math.floor(arr.length / 2)

  if (find < arr[mid]) {
    return binaryInsertion(arr.slice(0, mid), find)
  }
  return mid + binaryInsertion(arr.slice(mid), find)
}