Sort a large list fast (merge sort)
Coding problemMediumAsked in: Coupa
Given a list of integers, return it sorted from smallest to largest, using a sort you write yourself.
The list can hold 100,000 values, so the simple sorts that compare neighbours (bubble, selection, insertion) are too slow. Write an O(n log n) sort such as merge sort or quick sort, or a radix sort (it sorts by one digit or byte at a time; remember that values can be negative). The hidden tests include sorted, reverse-sorted and all-equal lists, which slow down a careless quick sort (one with a badly chosen pivot, the value it splits around).
Examples
Example 1
Input: nums = [5,2,3,1]
Output: [1,2,3,5]
Example 2
Input: nums = [5,1,1,2,0,0]
Output: [0,0,1,1,2,5]
Example 3
Input: nums = [-7]
Output: [-7]
Constraints
- The list holds between 0 and 100,000 integers
- Each value is a 32-bit integer
Run checks the 3 examples. Submit also runs the hidden tests: edge cases, large inputs and a time limit.
Run your code to see the results here. Ctrl or Cmd + Enter runs; add Shift to submit.