Merge Sort Implementation

Medium~20 min

Implement merge sort from scratch.

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

Merge sort is a divide-and-conquer algorithm:

  1. Divide the array into two halves
  2. Recursively sort each half
  3. Merge the two sorted halves into one sorted array

Do not use any built-in sort functions.

Examples

Example 1
Input: nums = [38, 27, 43, 3, 9, 82, 10]
Output: [3, 9, 10, 27, 38, 43, 82]
Explanation: The array is recursively split in half and merged back in sorted order.
Example 2
Input: nums = [5, 1, 4, 2]
Output: [1, 2, 4, 5]
Explanation: Split into [5,1] and [4,2]. Sort each half to get [1,5] and [2,4]. Merge to get [1,2,4,5].
Example 3
Input: nums = [1]
Output: [1]
Explanation: A single element is already sorted (base case).

Constraints

  • 1 <= nums.length <= 5000
  • -10^4 <= nums[i] <= 10^4
  • You must implement merge sort (do not use built-in sort)
Code
Ctrl+EnterRun|Ctrl+⇧+EnterSubmit
Output

Run your code to see results

Use Cmd+Enter to run