Merge Sort

Merge Sort is more advanced, divide-and-conquer algorithm that recursively splits an unsorted list into smaller sublists until each contains a single element. These sublists are then merged back together in a sorted manner. With a time complexity of O(n log n), Merge Sort is efficient and stable, making it suitable for handling large datasets.

Things to Observe

• Divide Recursively: Watch how the algorithm first breaks the array down recursively into single-element sub-arrays.
• Conquer (Merge): These sub-arrays are then merged back together in sorted order. This merging step is where the core sorting logic happens, comparing elements from the sub-arrays and placing them into a temporary array before updating the main one.

Pseudocode

function mergeSort(start, end):

    if start < end:

        mid = (start + end) / 2

        mergeSort(start, mid)

        mergeSort(mid + 1, end)

        merge(start, mid, end)