Merge Sort Problem

Merge sort divides the array into two halves until a range has zero or one element, which is already sorted. Merge the two sorted child ranges with pointers: repeatedly take the smaller front value, then append the unconsumed suffix. If equal elements should retain their original order, take from the left range first, making the algorithm stable. Copy the merged buffer back into the target range before returning so each parent receives sorted children. The correctness argument is induction: leaves are sorted, and merging two sorted lists produces one sorted list containing exactly their elements. Avoid allocating many temporary arrays in every recursive call when one reusable buffer can be passed down. Empty arrays, one element, duplicate values, negatives, and already sorted input should all work unchanged. There are log n levels and each level merges n elements, so time is O(n log n); standard array merge sort needs O(n) auxiliary space and O(log n) call-stack space.