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 time overall. Choosing from the left first on a tie makes the sort stable. The required input is an integer vector without missing values.
Articles by others on the same topic
There are currently no matching articles.