Courses Edexcel iGCSE Computer Science Algorithms Merge Sort

Merge Sort

Introduction to Merge Sort

Merge Sort is a popular sorting algorithm that follows the divide and conquer approach. The algorithm works by breaking down the list into smaller sub-lists and sorting them individually.

These sorted sub-lists are then merged back together to obtain the final sorted list.

Time & Space Complexity

Merge sort is a divide and conquer algorithm, it has a logarithmic time complexity of O(n log n)
Merge sort's space complexity is O(n)

What is a merge sort?

{"answers": {"A": "C - A sorting algorithm that finds the smallest element and puts it first", "B": "A - A sorting algorithm that repeatedly swaps adjacent elements", "C": "D - A sorting algorithm that divides the data in half and sorts each half", "D": "B - A sorting algorithm that puts elements into buckets"}, "question_text": "What is a merge sort?", "correct_answer": "C"}

Steps of Merge Sort

Divide the unsorted list into smaller sub-lists until each sub-list contains only one element.
Repeatedly merge adjacent sub-lists to produce new sorted sub-lists until there is only one sub-list remaining. This is done by comparing the elements of the sub-lists and merging them in the correct order.
The final sorted list is obtained when all sub-lists are merged.

Source: Wikipedia

Merge Sort in Python

def merge_sort(arr):
    if len(arr) <= 1: return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        result.append(left[i] if left[i] < right[j] else right[j])
        if left[i] < right[j]: i += 1
        else: j += 1
    return result + left[i:] + right[j:]

# Example
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))

Advantages of Merge Sort

Merge Sort guarantees a stable sort, which means that the order of equal elements is preserved.
It performs well on large lists and has a time complexity of O(n log n), where n is the number of elements in the list.

Merge Sort is a stable sorting algorithm. What does it mean?

{"answers": {"A": "It guarantees the worst-case time complexity of O(n log n).", "B": "It maintains the relative order of elements with equal keys.", "C": "It always sorts the array in ascending order.", "D": "It performs well for already partially sorted arrays."}, "question_text": "Merge Sort is a stable sorting algorithm. What does it mean?", "correct_answer": "B"}

Disadvantages of Merge Sort:

It is not an in-place sorting algorithm, meaning it needs extra storage proportional to the size of the input list.
Because it is usually implemented using recursion it can be difficult for beginner programmers to implement and understand.
Due to the extra setup it's not efficient for very small lists ( < 40 items)

What is a disadvantage of Merge Sort?

{"answers": {"A": "The worst-case time complexity is O(n^2).", "B": "Inefficient for small-sized arrays.", "C": "Requires additional memory space.", "D": "Not suitable for sorting numbers."}, "question_text": "What is a disadvantage of Merge Sort?", "correct_answer": "C"}

Review: Fill in the Blanks

Merge Sort is a popular sorting algorithm that follows the approach. The algorithm works by breaking down the list into smaller and sorting them individually. These sorted sub-lists are then merged back together to obtain the final sorted list. Merge sort has a time complexity of and a space complexity of .

The steps of Merge Sort include first dividing the unsorted list into smaller sub-lists until each sub-list contains only one . Next, adjacent sub-lists are repeatedly to produce new sorted sub-lists until there is only one sub-list remaining. The final sorted list is obtained when all sub-lists are merged together.

One of the main advantages of Merge Sort is that it guarantees a sort, which means that the order of equal elements is preserved. Additionally, it performs well on large lists due to its of O(n log n). However, Merge Sort has its disadvantages; it is not an sorting algorithm, meaning it requires extra storage proportional to the size of the input list. Furthermore, since it is usually implemented using , it can be difficult for beginner programmers to understand and implement.

Click the keywords below to fill in the blanks:

Element O(N) Stable Merged Sub-Lists In-Place Recursion Time Complexity O(N Log N) Divide And Conquer

✓ All blanks filled correctly! Great job!