Practice/Amazon/Leetcode 912. Sort an Array

Leetcode 912. Sort an Array

CodingMust

Problem

Implement the merge sort algorithm to sort an array of integers in ascending order. You must write the sorting logic from scratch without using any built-in sorting functions.

Merge sort is a divide-and-conquer algorithm that splits the array into smaller subarrays, sorts them recursively, and then merges the sorted subarrays back together. Your implementation should demonstrate understanding of this recursive approach.

Requirements

1. Implement merge sort without using built-in sort functions like sort(), sorted(), etc.
2. The function should sort the array in-place or return a new sorted array
3. Handle arrays containing negative numbers, positive numbers, and zeros
4. Preserve duplicate values in the sorted output
5. Your solution must achieve O(n log n) time complexity

Constraints

• 0 <= nums.length <= 50000
• -50000 <= nums[i] <= 50000
• Time complexity must be O(n log n)
• Space complexity should be O(n) for the merge operation

Examples

Example 1:

Input: nums = [5, 2, 8, 1, 9] Output: [1, 2, 5, 8, 9] Explanation: The array is sorted in ascending order.

Example 2:

Input: nums = [3, 1, 4, 1, 5, 9, 2, 6, 5] Output: [1, 1, 2, 3, 4, 5, 5, 6, 9] Explanation: Duplicate elements (1 and 5) are preserved in the sorted result.

Example 3:

Input: nums = [-5, 3, -1, 7, -8, 0, 4] Output: [-8, -5, -1, 0, 3, 4, 7] Explanation: Negative numbers are sorted before positive numbers.