Merge Sort

Merge Sort is a highly efficient, stable, comparison-based sorting algorithm. It's a classic example of the "divide and conquer" paradigm.

The merge step is the core of the algorithm. It takes two sorted sublists and combines them into a single sorted list. This is done by comparing the first elements of each sublist and adding the smaller one to the new list. This process is repeated until one of the sublists is empty, at which point the remaining elements of the other sublist are appended to the new list.

Merge Sort has a time complexity of O(n log n) in all cases (worst, average, and best), making it a very reliable choice for sorting. Its main disadvantage is that it requires O(n) additional space for the temporary array used in the merge step.

Merge Sort Visualization

Step 1 of 0

Current Action

Ready to start

Phase

Ready

Recursion Depth

Left Array Pointer

Right Array Pointer

Merge Position (M)

Being Merged

Active Range

Not Active

Divide & Conquer: Merge sort recursively divides the array into halves until single elements remain, then merges sorted halves back together. Stable sort with guaranteed O(n log n) time complexity.

Merge Sort Algorithm

Merge Sort is a highly efficient, stable, comparison-based sorting algorithm. It's a classic example of the "divide and conquer" paradigm.

Algorithm Steps

Divide: Recursively divide the array into two halves until each subarray contains a single element.
Conquer: Starting with the single-element subarrays, merge them into new sorted subarrays.
Combine: Repeat the merging process until you have one sorted array.

Merge Sort


def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        left_half = arr[:mid]
        right_half = arr[mid:]

        merge_sort(left_half)
        merge_sort(right_half)

        i = j = k = 0

        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1

        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1

        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1