912. Sort an Array

Description

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

 

Solutions

Solution: Merge Sort

• Time complexity: O(nlogn)
• Space complexity: O(n)

 

JavaScript

/**
 * @param {number[]} nums
 * @return {number[]}
 */
const sortArray = function (nums) {
  if (nums.length <= 1) return nums;

  const mid = Math.floor(nums.length / 2);
  const prefix = nums.slice(0, mid);
  const suffix = nums.slice(mid);

  const mergeSort = (nums1, nums2) => {
    const result = [];
    let a = 0;
    let b = 0;

    while (a < nums1.length && b < nums2.length) {
      const num = nums1[a] < nums2[b] ? nums1[a++] : nums2[b++];

      result.push(num);
    }
    while (a < nums1.length) result.push(nums1[a++]);
    while (b < nums2.length) result.push(nums2[b++]);

    return result;
  };

  return mergeSort(sortArray(prefix), sortArray(suffix));
};