In-place merge
= In-place merge
Combining adjacent <sorted runs> within their existing <array> segment. A simple constant-auxiliary-space version moves the smaller second-run head before the first-run head by shifting the intervening block one place right. The finished prefix is always a merge of the consumed portions. This can use quadratic <running time>; minimizing storage does not automatically preserve the linear cost of a disjoint-output merge.