Apply merge sort

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.

Exercise 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)).

Show example 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))

Test yourself

Slice

return sorted_scores[____:]

Show answer

return sorted_scores[-k:]

Apply merge sort: match the terms

Top k

[-k:]
Bottom k

[:k]
Last element

[-1]
First element

[0]
What is used for top 3?
- sorted_scores[:3]
- sorted_scores[-1]
- sorted_scores[3]
- sorted_scores[-3:]
Show answer

sorted_scores[-3:] — sorted_scores[-3:]

Next lesson: Print statistics

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies