Hand-Rolled Sort

Medium

You are given an integer array values. Return it sorted in non-decreasing order. The point is to implement the sorting yourself: do not use the built-in sort/sorted or their equivalents. Aim for O(n log n) time and as little extra memory as you can manage.

Example 1

values=[9, -4, 0, 7, -4] → [-4, -4, 0, 7, 9]

In ascending order: -4, -4, 0, 7, 9. Equal values all stay and simply end up next to each other.

Example 2

values=[3, 2, 1] → [1, 2, 3]

The array was in descending order; sorted, it reads 1, 2, 3.

Example 3

values=[42] → [42]

Constraints

1 ≤ len(values) ≤ 5·10⁴
-5·10⁴ ≤ values[i] ≤ 5·10⁴

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Divide and Conquer Bucket Sort Counting Sort Radix Sort Sorting Heap (Priority Queue)Merge Sort

Similar problems

Most Common Values Medium K-th Code by Its Last Digits Medium Widest Gap When Sorted Medium K-th Highest Score Medium Most Searched Words Medium

Input

values=[9, -4, 0, 7, -4]

Expected

[-4, -4, 0, 7, 9]

Run checks the first 3 tests in your browser. Submit checks all 8 tests on the server, hidden ones included.