= Solution
Recursively sort two halves, then merge their increasing lists by repeatedly choosing the smaller current first element. The following function preserves repetitions, as sorting a vector should:
``
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
}
``
<Induction> proves correctness: each recursive result is sorted and preserves its input <multiset>; each merge step removes the least remaining element from one of them, so the output is sorted and has exactly the union <multiset>. The base case has length one. Each merge takes linear time, yielding $O(n\log n)$ time overall. Choosing from the left first on a tie makes the sort stable. The required input is an integer vector without missing values.
Back to article page
