Merge Sort

What is Merge Sort?

The merge sort algorithm has two parts: splitting items and merging items. It starts by splitting a list into halves called sublists, repeating until each sublist contains only single items.

The merge sort algorithm is an example of a divide and conquer approach. It breaks down a problem into smaller parts until they are simple enough to solve directly.

• Splitting: Repeatedly dividing the group into half until you have separate groups with a single item.
• Merging: Reassembling groups by comparing the first items of two sublists and placing the lowest value into a new ordered list.

Numerical Example: Olympic Medals

Sorting medal counts: [15, 25, 13, 29, 18].

Sorting Words: Computer Scientists

Sorting famous pioneers alphabetically: ["Ada Lovelace", "Grace Hopper", "Anita Borg", "Margaret Hamilton", "Annie Easley", "Joan Clarke", "Mary Wilkes", "Karen Spärck Jones"].

Algorithm Implementation

The instructions for merge sort involve a recursive logic of splitting and merging.

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

def merge(left, right):
    result = []
    while left and right:
        if left[0] <= right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    result.extend(left if left else right)
    return result

Efficiency Scenarios

Unlike Bubble Sort, Merge Sort always splits the list regardless of its initial order.