Implement merge sort and explain the merge operation.

Divide array into halves recursively until single elements. Merge combines two sorted halves: use two pointers, compare elements at each pointer, copy smaller to result array, advance that pointer. Continue until one half exhausted, then copy remaining. Key insight: merging two sorted arrays is O(n). Total complexity: T(n) = 2T(n/2) + O(n) = O(n log n) by Master theorem. Space O(n) for merge buffer.