Apply merge sort
- Algorithms course
- Intermediate
- Lesson 23/80
- 4 min
Sort scores with merge sort.
Pick top N
We will pick the top k from the sorted array. Since the sorted array goes small to large, the largest are at the end and easy to take.
sorted_scores[-k:] gives us the last k elements. These are the top k scores; their order is preserved.
For top 3 we expect [88, 90, 92]; that is the three highest scores.
Negative index
In Python arr[-k:] gives the last k elements. [-1] is the last element, [-2:] the last two elements.
This is shorter and more readable than writing arr[len(arr)-k:]. Ideal for taking the largest from a sorted array and widely used.
For the smallest k use arr[:k]; this slices from the start and gives the smallest values.
Practice Pick top N
Write top_k(scores, k). Sort first, then return the top k. Print [88, 90, 92] with print(top_k(init_scores(), 3)).
Starter code
def init_scores():
# Return score array
return [85, 92, 78, 90, 88]
def merge_sort_scores(scores):
# Sort scores
if len(scores) <= 1:
return scores
mid = len(scores) // 2
left = merge_sort_scores(scores[:mid])
right = merge_sort_scores(scores[mid:])
return merge(left, right)
def top_k(scores, k):
# Take top kSample solution
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i]); i += 1
else:
result.append(right[j]); j += 1
result.extend(left[i:]); result.extend(right[j:])
return result
def init_scores():
# Return score array
return [85, 92, 78, 90, 88]
def merge_sort_scores(scores):
# Sort scores
if len(scores) <= 1:
return scores
mid = len(scores) // 2
left = merge_sort_scores(scores[:mid])
right = merge_sort_scores(scores[mid:])
return merge(left, right)
def top_k(scores, k):
# Take top k
sorted_scores = merge_sort_scores(scores)
return sorted_scores[-k:]
print(top_k(init_scores(), 3))Expected output
[88, 90, 92]
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Slice
return sorted_scores[____:]return sorted_scores[-k:]Explanation: -k is right.
2 Apply merge sort: match the terms
| Term | Meaning |
|---|---|
Top k |
[-k:] |
Bottom k |
[:k] |
Last element |
[-1] |
First element |
[0] |
3 What is used for top 3?
- sorted_scores[:3]
- sorted_scores[-1]
- sorted_scores[3]
- sorted_scores[-3:] Correct answer
Explanation: sorted_scores[-3:]