912. Sort an Array

[mah-shamim]

Given an array of integers nums, sort the array in ascending order and return it.

You must solve the problem without using any built-in functions in O(nlog(n)) time complexity and with the smallest space complexity possible.

Example 1:

• Input: nums = [5,2,3,1]
• Output: [1,2,3,5]
• Explanation: After sorting the array, the positions of some numbers are not changed (for example, 2 and 3), while the positions of other numbers are changed (for example, 1 and 5).

Example 2:

• Input: nums = [5,1,1,2,0,0]
• Output: [0,0,1,1,2,5]
• Explanation: Note that the values of nums are not necessairly unique.

Constraints:

• 1 <= nums.length <= 5 * 104
• -5 * 104 <= nums[i] <= 5 * 104

[mah-shamim]

To solve this problem, we can follow these steps:

1. Divide: Recursively divide the array into two halves until each subarray contains a single element.
2. Conquer: Merge the sorted halves to produce sorted subarrays.
3. Combine: Continue merging the subarrays until we get the final sorted array.

Let's implement this solution in PHP: 912. Sort an Array

<?php
// Example usage:
$nums1 = [5, 2, 3, 1];
$result1 = sortArray($nums1);

echo implode(", ", $result1); // Output: 1, 2, 3, 5

// Example usage:
$nums2 = [5,1,1,2,0,0]
$result2 = sortArray($nums2);

echo implode(", ", $result2); // Output: 0,0,1,1,2,5

// Example usage:
$nums3 = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,160,161,162,163,164,165,166,167,168,169,170,171,172,173,174,175,176,177,178,179,180,181,182,183,184,185,186,187,188,189,190,191,192,193,194,195,196,197,198,199,200,201,202,203,204,205,206,207,208,209,210,211,212,213,214,215,216,217,218,219,220,221,222,223,224,225,226,227,228,229,230,231,232,233,234,235,236,237,238,239,240,241,242,243,244,245,246,247,248,249,250,251,252,253,254,255,256,257,258,259,260,261,262,263,264,265,266,267,268,269,270,271,272,273,274,275,276,277...];
$result3 = sortArray($nums3);

echo implode(", ", $result3); // Output: 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,160,161,162,163,164,165,166,167,168,169,170,171,172,173,174,175,176,177,178,179,180,181,182,183,184,185,186,187,188,189,190,191,192,193,194,195,196,197,198,199,200,201,202,203,204,205,206,207,208,209,210,211,212,213,214,215,216,217,218,219,220,221,222,223,224,225,226,227,228,229,230,231,232,233,234,235,236,237,238,239,240,241,242,243,244,245,246,247,248,249,250,251,252,253,254,255,256,257,258,259,260,261,262,263,264,265,266,267,268,269,270,271,272,273,274,275,276,277...

?>

Explanation:

1. mergeSort Function:

   • The mergeSort function checks if the array has one or no elements (base case). If true, it returns because the array is already sorted.
   • It then splits the array into two halves (left and right).
   • It recursively calls mergeSort on each half.
   • Finally, it merges the sorted halves using the merge function.

2. merge Function:

   • The merge function takes three parameters: the original array, and the two halves (left and right).
   • It initializes three pointers (i, j, and k) for traversing the left, right, and original arrays, respectively.
   • It compares the elements from left and right, and places the smaller element into the original array.
   • It handles any remaining elements in the left or right arrays after the main loop.

3. sortArray Function:

   • The sortArray function is a wrapper that calls the mergeSort function and returns the sorted array.

This implementation ensures the array is sorted in (O(n \log n)) time complexity and uses (O(n)) space complexity. This is efficient and meets the problem constraints.