Merge sort is the canonical divide-and-conquer algorithm. Divide the array into two halves, recursively sort each half, then merge the two sorted halves into one sorted array. The merge step walks two sorted runs with two pointers, always taking the smaller front element.
Merge sort: divide, conquer, then mergeThe recursion tree is perfectly balanced: each level halves the input, so there are O(log n) levels, and each level does O(n) work in merging. That gives a guaranteed O(n log n) time even in the worst case - at the price of O(n) auxiliary space for the merge buffer.