Sorting

Quick Sort (Lomuto)

Choose the last item as a pivot, partition smaller values to its left, then recurse on the two sides.

Algorithm

Basic Implementation

basic.f90 
program sort_quick_lomuto
    implicit none
    integer :: arr(5) = [4, 1, 5, 2, 3]
    call quick_sort(arr, 1, 5)
    print '(*(I0,1X))', arr
contains
    integer function partition(arr, low, high)
        integer, intent(inout) :: arr(:)
        integer, intent(in) :: low, high
        integer :: pivot, i, j, tmp
        pivot = arr(high)
        i = low - 1
        do j = low, high - 1
            if (arr(j) <= pivot) then
                i = i + 1
                tmp = arr(i); arr(i) = arr(j); arr(j) = tmp
            end if
        end do
        tmp = arr(i + 1); arr(i + 1) = arr(high); arr(high) = tmp
        partition = i + 1
    end function partition

    recursive subroutine quick_sort(arr, low, high)
        integer, intent(inout) :: arr(:)
        integer, intent(in) :: low, high
        integer :: pivot_index
        if (low < high) then
            pivot_index = partition(arr, low, high)
            call quick_sort(arr, low, pivot_index - 1)
            call quick_sort(arr, pivot_index + 1, high)
        end if
    end subroutine quick_sort
end program sort_quick_lomuto

The pinned first partition uses [4, 1, 5, 2, 3] with pivot 3. The diagrams track the boundary, swaps, and recursive ranges.

Step 1 - Choose the last value as pivot

The pivot is arr[4] = 3, and i starts just before the current range.

Initial partition state for [4, 1, 5, 2, 3].i0i1i2i3i441523j startspivot

Step 2 - Swap small values left

1 and 2 are <= pivot, so they move into the left partition.

After scanning values before the pivot: [1, 2, 5, 4, 3].i0i1i2i3i412543<= 3<= 3> 3> 3pivot

Step 3 - Place pivot, then recurse

Swapping pivot 3 into index 2 gives [1, 2, 3, 4, 5]; recurse on [1, 2] and [4, 5].

Pivot lands at index 2 and splits the remaining work.left rangepivotright range[1, 2]3 at i2[4, 5]quick_sort(0,1)fixedquick_sort(3,4)

Complexity

  • Time: O(n^2) worst, O(n log n) average
  • Space: O(log n) average call stack
  • Stable: no

Implementation notes

  • Keep the explicit algorithmic steps instead of calling a standard-library sort. This checked-in replay shows each comparison and swap in the first partition, then summarizes the recursive calls on already-sorted sides.
  • The implementation is intentionally compact for learning and replay, not a production sorting utility.
pivot The final element is moved to the boundary between smaller and larger values.
partition One scan rearranges the current range before the recursive calls.