Merge Sort: The Principle of Merge Sort and a Classic Application of Divide and Conquer Thought

Merge sort is based on the "divide and conquer" principle, with core steps including decomposition, recursion, and merging. It first recursively splits an array into subarrays of length 1, then merges adjacent ordered subarrays using a two-pointer technique (comparing element sizes and storing results in a temporary array). The complete process involves decomposing until the smallest subarrays are reached, then merging them layer by layer into an ordered array. The time complexity is stably O(n log n) (recursive depth is log n, and each layer requires traversing all elements during merging). The space complexity is O(n) due to the temporary array needed for storing merged results. As a stable sorting algorithm, the relative order of equal elements remains unchanged, making it suitable for large datasets or scenarios requiring stability. Its "decomposition-merge" logic intuitively embodies the divide and conquer concept, serving as a classic case for understanding recursion and simplifying complex problems.