What is Merge Sort?

Steps of Merge Sort

1. Divide the array into halves until each part has a single element.
2. Recursively sort and merge each half back together to form a sorted array.

Merge Sort Example

Array before sorting: [5, 3, 8, 4, 2]

1. Divide into [5, 3] and [8, 4, 2]
2. Divide further until single elements: [5], [3], [8], [4], [2]
3. Merge back in sorted order to get [2, 3, 4, 5, 8]

Time and Space Complexity

Time Complexity: O(n log n) for all cases

Space Complexity: O(n) for auxiliary array space

Pseudo Code for Merge Sort

Begin
  if left < right
    mid = (left + right) / 2
    mergeSort(arr, left, mid)
    mergeSort(arr, mid + 1, right)
    merge(arr, left, mid, right)
End
            

Merge Sort Visualization

void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}