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.
For scalar minimization, apply Newton's root-finding method to the stationarity equation . Linearize at the current point to obtainThe iteration requires . Near a nondegenerate local minimum, where , , suitable smoothness and a sufficiently close starting value give local convergence. A stationary limit must still be checked to be a minimum. This undamped method is not globally convergent and need not decrease at every step.
Let , with , . Taylor expansion givesDivision in the Newton update yieldsThus convergence is generically quadratic when that coefficient is nonzero. With a locally Lipschitz second derivative and nonzero , the weaker estimate also proves local quadratic convergence.
“Quadratic at best” is false as a universal upper bound. If the displayed coefficient vanishes, the order can be higher. For example has a minimum at zero, and its Newton optimization update is , which has cubic convergence. For a nondegenerate quadratic objective the method reaches the stationary point in one step. The expansion proves the standard generic quadratic statement while retaining and correcting the source's stronger wording explicitly.
Here and . This implementation uses the undamped Newton step, checks a stationary point's curvature, and reports failure on a two-cycle or exhausted iteration limit:
R
newton_min <- function(x0, tol = 1e-10, maxit = 100L) {
fp <- function(x) 4*x^3 - 12*x^2 + 4*x + 12
fpp <- function(x) 12*x^2 - 24*x + 4
x <- x0
trace <- x
for (k in seq_len(maxit)) {
g <- fp(x)
h <- fpp(x)
if (abs(g) <= tol) {
return(list(x = x, converged = h > 0,
reason = if (h > 0) "minimum" else "not a strict minimum",
trace = trace))
}
if (!is.finite(h) || abs(h) <= .Machine$double.eps)
stop("Newton step has zero or invalid curvature")
next_x <- x - g/h
if (!is.finite(next_x)) stop("Nonfinite Newton iterate")
trace <- c(trace, next_x)
n <- length(trace)
if (n >= 3L && abs(trace[n] - trace[n - 2L]) <= tol*(1 + abs(next_x)))
return(list(x = next_x, converged = FALSE,
reason = "two-cycle", trace = trace))
x <- next_x
}
list(x = x, converged = FALSE, reason = "iteration limit", trace = trace)
}A sufficiently close start near converges to the minimum. The derivative cubic has exactly one real root: after it is proportional to , whose local maximum and minimum are both positive, so it crosses zero only once, on the left. Since the quartic tends to in both directions and its curvature at that stationary point is positive, this is the unique global minimum. The function reports convergence rather than assuming that every starting point must reach it.
At , the derivative and curvature are , , so the next iterate is . At , they are , , so the next iterate is . HenceThe undamped algorithm does not converge to a minimum; it has an exact two-cycle. The implementation in (iii) detects this after returning to one and reports failure. This example illustrates why the local convergence result in (ii) does not justify global success.
Articles by others on the same topic
There are currently no matching articles.