Sort an Array
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Sort an array of integers in ascending order without using built-in sort.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1How do you merge two sorted lists into one sorted list?
- Hint 2What is the base case of the splitting?
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
Sorting a big stack of exam papers by marks. Split the stack into two heaps, give each to a friend with the same instruction, and each returns a sorted heap. You then merge: look at the top paper of each heap, take the one with the lower marks, and repeat until both heaps are empty. A heap of a single paper is already sorted.
- The obvious way
Bubble or selection sort: O(n²).
- The key insight
If the list has 0 or 1 items return it. Otherwise split at the middle, sort both halves recursively, then merge: keep a position in each half, repeatedly take the smaller front item, finally append what remains. Each level of splitting does O(n) work and there are log n levels.
- The algorithm
- 0 or 1 item: already sorted.
- Split at the middle; sort each half recursively.
- Merge by repeatedly taking the smaller front item.
- Append the leftovers.
Watch it run
Examplenums = [5, 2, 3, 1]
Split into [5, 2] and [3, 1], then each into single papers (already sorted).
split
Where people slip
- Use <= when comparing fronts so equal items keep their order (a stable sort).
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def sort_array(nums):
if len(nums) <= 1:
return nums # one paper is already sorted
middle = len(nums) // 2
left_heap = sort_array(nums[:middle]) # a friend sorts each heap
right_heap = sort_array(nums[middle:])
merged = []
left_position = right_position = 0
while left_position < len(left_heap) and right_position < len(right_heap):
if left_heap[left_position] <= right_heap[right_position]:
merged.append(left_heap[left_position]) # the lower top paper goes first
left_position += 1
else:
merged.append(right_heap[right_position])
right_position += 1
merged.extend(left_heap[left_position:]) # whatever is left of one heap
merged.extend(right_heap[right_position:])
return mergedNow close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.