挿入ソート、マージソート

# ソートされた配列arrにnumを入れ、ソートされた配列を返す
def insert(arr, num)
  return [num] if arr.empty?

  if arr[0] < num
    [arr[0], *insert(arr[1..-1], num)]
  else
    [num, *arr]
  end
end

def insertSort(arr)
  return arr if arr.empty?

  insert(insertSort(arr[1..-1]), arr[0])
end

# ソートされた2つの配列arr1,arr2を合わせ、ソートされた配列を返す
def merge(arr1, arr2)
  return arr1 if arr2.empty?
  return arr2 if arr1.empty?

  if arr1[0] < arr2[0]
    [arr1[0], *merge(arr1[1..-1], arr2)]
  else
    [arr2[0], *merge(arr1, arr2[1..-1])]
  end
end

def mergeSort(arr)
  return arr if arr.length == 1

  halfIdx = arr.length / 2
  merge(mergeSort(arr[0..halfIdx-1]), mergeSort(arr[halfIdx..-1]))
end

ループで書くとtmpに保存して...とかやるから気づきにくいけど
再帰で書いてみるとinsertとmergeが似てることに気づく。