 Solution

R
merge_sort <- function(x) {
  n <- length(x)
  stopifnot(n >= 1L)
  if (n == 1L) return(x)
  m <- n %/% 2L
  left <- merge_sort(x[seq_len(m)])
  right <- merge_sort(x[(m + 1L):n])
  nl <- length(left)
  nr <- length(right)
  out <- integer(n)
  i <- j <- k <- 1L
  while (i <= nl && j <= nr) {
    if (left[i] <= right[j]) {
      out[k] <- left[i]
      i <- i + 1L
    } else {
      out[k] <- right[j]
      j <- j + 1L
    }
    k <- k + 1L
  }
  if (i <= nl) out[k:n] <- left[i:nl]
  if (j <= nr) out[k:n] <- right[j:nr]
  out
}