Sort an Array
Sort an Array is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Greedy Patterns pattern, in the Sorting Based subpattern.
Problem statement
Given nums, an array of integers, arrange all of its elements in ascending order. Ascending order means each element is less than or equal to the element that follows it, so duplicate values remain present with the same frequency.
Return the sorted array. Do not call any built-in sorting function, and use an algorithm whose running time is O(n log n), where n is the length of nums.
The returned array must contain exactly the same integers as the input, including repeated values. An input with one element is already sorted.
Example 1:
Input: nums = [8,-3,4,4,1] Output: [-3,1,4,4,8] Explanation: The values are rearranged from smallest to largest, while both occurrences of 4 are retained.
Example 2:
Input: nums = [6,2,9,0,-5,3] Output: [-5,0,2,3,6,9] Explanation: Sorting the six values in nondecreasing order produces the returned array.
Example 3:
Input: nums = [7,7,7] Output: [7,7,7] Explanation: All values are equal, so their order does not change.
Constraints:
- 1 <= nums.length <= 5 10^4 - -5 10^4 <= nums[i] <= 5 10^4 - nums is a JSON array of integers. - The input contains at least one integer.
Topics and companies
Topics: Array, Sorting, Divide and Conquer, Recursion.
How to practise Sort an Array on Thita.ai
Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n log n) time and O(n) auxiliary space, plus O(log n) recursion stack space.
Open Sort an Array in the code editor, or read the Sort an Array editorial for a worked solution with its approach and complexity analysis.
Where Sort an Array sits in the DSA pattern sheet
- Greedy Patterns pattern guide
- Sorting Based subpattern
- The full DSA patterns sheet
- All coding practice problems
Problems related to Sort an Array
Other problems that use the same Sorting Based and Greedy Patterns techniques:
- Assign Cookies — Easy, same subpattern
- Candy — Hard, same subpattern
- Hand of Straights — Medium, same subpattern
- Lemonade Change — Easy, same subpattern
- Merge Triplets to Form Target Triplet — Medium, same subpattern
- Queue Reconstruction by Height — Medium, same subpattern