How do you solve Sort an Array on LeetCode?

Sort an Array (LeetCode #912) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n log n) time complexity and O(n) space complexity. Key insight: Understanding the difference between O(n²) and O(n log n) algorithms is crucial.

What is the brute force solution for Sort an Array?

The brute force approach for Sort an Array is Brute Force, with O(n²) time complexity and O(1) space complexity. The simplest way to sort an array is to use a basic sorting algorithm like Bubble Sort or Selection Sort. These algorithms repeatedly compare and swap elements until the entire array is sorted. The optimal Optimal Solution approach improves this to O(n log n).

What are the interview tips for Sort an Array?

Always explain your thought process clearly. Consider edge cases, like empty arrays or arrays with one element. Practice implementing both brute force and optimal solutions.

What are common mistakes when solving Sort an Array?

Not understanding the base case in recursive algorithms. Confusing the merge process with sorting individual elements.

#912

Sort an Array

Medium

ArrayDivide and ConquerSortingHeap (Priority Queue)Merge SortBucket SortRadix SortCounting SortDivide and ConquerMerge Sort

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n log n)
Space	O(1)	O(n)

💡

Intuition

Time O(n log n)Space O(n)

Using a more efficient sorting algorithm like Merge Sort allows us to sort the array in O(n log n) time. Merge Sort divides the array into smaller parts, sorts them, and then merges them back together.

⚙️

Algorithm

4 steps

1Step 1: If the array has one or zero elements, return it as it is already sorted.
2Step 2: Divide the array into two halves.
3Step 3: Recursively sort both halves.
4Step 4: Merge the two sorted halves back together.

solution.py27 lines

1# Full working Python code
2
3def merge_sort(nums):
4    if len(nums) <= 1:
5        return nums
6    mid = len(nums) // 2
7    left = merge_sort(nums[:mid])
8    right = merge_sort(nums[mid:])
9    return merge(left, right)
10
11
12def merge(left, right):
13    sorted_array = []
14    i = j = 0
15    while i < len(left) and j < len(right):
16        if left[i] < right[j]:
17            sorted_array.append(left[i])
18            i += 1
19        else:
20            sorted_array.append(right[j])
21            j += 1
22    sorted_array.extend(left[i:])
23    sorted_array.extend(right[j:])
24    return sorted_array
25
26# Example usage
27print(merge_sort([5, 2, 3, 1]))

ℹ

Complexity note: The time complexity is O(n log n) because we divide the array in half log(n) times and merge the sorted halves in linear time. The space complexity is O(n) due to the additional arrays created during the merge process.

1Understanding the difference between O(n²) and O(n log n) algorithms is crucial.
2Recognizing when to use recursion and how it helps in divide-and-conquer strategies.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.