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.
New to topics? Read the docs here!