Merge Sort (Top-Down)

Split the array recursively, sort each half, then merge two sorted runs into one sorted result.

Algorithm

Basic Implementation

basic.f90

program sort_merge
    implicit none
    integer :: arr(5) = [5, 1, 4, 2, 8]
    call merge_sort(arr, 1, 5)
    print '(*(I0,1X))', arr
contains
    recursive subroutine merge_sort(arr, left, right)
        integer, intent(inout) :: arr(:)
        integer, intent(in) :: left, right
        integer :: mid
        if (left >= right) return
        mid = (left + right) / 2
        call merge_sort(arr, left, mid)
        call merge_sort(arr, mid + 1, right)
        call merge(arr, left, mid, right)
    end subroutine merge_sort

    subroutine merge(arr, left, mid, right)
        integer, intent(inout) :: arr(:)
        integer, intent(in) :: left, mid, right
        integer :: tmp(5), i, j, k, t
        i = left; j = mid + 1; k = 1
        do while (i <= mid .and. j <= right)
            if (arr(i) <= arr(j)) then
                tmp(k) = arr(i); i = i + 1
            else
                tmp(k) = arr(j); j = j + 1
            end if
            k = k + 1
        end do
        do while (i <= mid)
            tmp(k) = arr(i); i = i + 1; k = k + 1
        end do
        do while (j <= right)
            tmp(k) = arr(j); j = j + 1; k = k + 1
        end do
        do t = 1, k - 1
            arr(left + t - 1) = tmp(t)
        end do
    end subroutine merge
end program sort_merge

The pinned input is [5, 1, 4, 2, 8]. The diagrams show the split into recursive halves, the sorted subarrays, and the final merge choices.

Step 1 - Split the input

The first midpoint splits [5, 1, 4, 2, 8] into left [5, 1] and right [4, 2, 8].

Step 2 - Sorted halves return

Recursive calls return [1, 5] and [2, 4, 8] before the final merge begins.

Step 3 - Merge by taking smaller fronts

Take 1 from left, then 2 and 4 from right, then the remaining 5 and 8.

Complexity

Time: O(n log n)
Space: O(n)
Stable: yes

Implementation notes

Keep the explicit algorithmic steps instead of calling a standard-library sort. The replay is meant to expose comparisons, movement, and recursion.
The implementation is intentionally compact for learning and replay, not a production sorting utility.

divide and conquer Each recursive call solves a smaller sorted subproblem.

merge step Two sorted halves are combined by repeatedly taking the smaller front item.