Merge Sort

Merge sort is an efficient, general-purpose sorting algorithm that uses a divide and conquer strategy. It works by repeatedly splitting a list in half until each sub-list contains a single element, and then merging those sub-lists back together in the correct order.

---

The Divide and Conquer Approach

Merge sort follows three key steps:

1. Divide — Split the list into two halves.
2. Conquer — Recursively sort each half (keep splitting until each sub-list has one element).
3. Combine — Merge the sorted halves back together to produce the final sorted list.

A list of one element is considered already sorted (this is the base case for the recursion).

---

Pseudocode for Merge Sort

FUNCTION mergeSort(list)
    IF LENGTH(list) <= 1 THEN
        RETURN list
    ENDIF
    mid = LENGTH(list) DIV 2
    left = mergeSort(list[0 TO mid - 1])
    right = mergeSort(list[mid TO end])
    RETURN merge(left, right)
ENDFUNCTION