Merge Sort

Description
Merge sort is a sorting algorithm based on the divide and conquer strategy. It recursively divides the array into two halves, sorts the left and right parts separately, and then merges the two sorted arrays into one sorted array. The time complexity of merge sort is O(n log n), and it is a stable sorting algorithm.

Divide and Conquer Concept

1. Divide: Split the current array into left and right subarrays from the middle position.
2. Conquer: Recursively perform merge sort on the left and right subarrays (until the subarray length is 1, which is naturally sorted).
3. Combine: Merge the two sorted subarrays into one sorted array.

Detailed Explanation of the Merge Process
Merging is the core step of merge sort, ensuring that the merged array is sorted. The specific process is as follows:

1. Create a temporary array to store the merged result and initialize the starting indices of the left and right subarrays (e.g., leftIndex and rightIndex).
2. Compare the current elements pointed to by the left and right subarrays, place the smaller one into the temporary array, and move the corresponding index.
3. If all elements of one subarray have been merged, directly append the remaining elements of the other subarray to the end of the temporary array.
4. Copy the temporary array back to the corresponding position in the original array.

Example Demonstration
Taking the array [38, 27, 43, 3, 9, 82, 10] as an example:

1. Divide:

   • First level: Divide into [38, 27, 43, 3] and [9, 82, 10].
   • Second level: The left half is further divided into [38, 27] and [43, 3], and the right half is divided into [9, 82] and [10].
   • Continue dividing until each subarray has a length of 1.

2. Merge and Sort (starting from the bottom level):

   • Merge [38] and [27]: After comparison, obtain [27, 38].
   • Merge [43] and [3]: Obtain [3, 43].
   • Merge [27, 38] and [3, 43]:
     • Compare 27 and 3 → Place 3; compare 27 and 43 → Place 27; compare 38 and 43 → Place 38; place the remaining 43. Result: [3, 27, 38, 43].
   • The right half is processed similarly, and finally, the two large blocks are merged to obtain the fully sorted array.

Key Points of Algorithm Implementation

• Recursive Base Case: Return directly when the subarray length is ≤ 1.
• Space Complexity: Merging requires O(n) temporary space, but this can be optimized by globally allocating space once to avoid repeated allocations.
• Stability: When merging, prioritize taking elements from the left subarray for equal elements to maintain the original order.

Summary
Merge sort reduces the problem size through the divide and conquer approach and solves subproblems through merging operations. Its time complexity is consistently O(n log n), but it requires extra space, making it suitable for scenarios with large datasets and stability requirements (such as external sorting).