Fortran sorting
last modified November 14, 2026
Sorting means arranging values so that each one is no greater than the next. Fortran has no intrinsic sort subroutine for arrays, so a program either calls an external library or carries a dozen lines of its own. The algorithms below are the classic ones: bubble, insertion and selection sort, which are short and slow, and merge and quick sort, which are longer and much faster. The article also shows how to sort records by a chosen key with a comparison procedure, and how to sort an index array instead of the data.
Two words recur throughout. A sort is stable when values that compare
equal keep their original relative order, and in place when it needs
only a fixed amount of extra memory beyond the array itself. The running time
is described by how it grows with the number of elements n: the
simple sorts need time proportional to n**2, the fast ones to
n * log(n), which for a thousand elements is about a hundred times
less work.
Bubble sort
Bubble sort compares neighbours and swaps them when they are out of order, and repeats the pass until nothing moves. The version below stores whether a pass made a swap and leaves early when it did not, so an already sorted array costs a single pass. Two counters report how much work was done, which makes the quadratic behaviour visible on a small example.
module bubbles
implicit none
private
public :: bubble
contains
subroutine bubble(a, passes, comps)
integer, intent(inout) :: a(:)
integer, intent(out) :: passes, comps
integer :: i, j, t
logical :: swapped
passes = 0
comps = 0
do i = 1, size(a) - 1
passes = passes + 1
swapped = .false.
do j = 1, size(a) - i
comps = comps + 1
if (a(j) > a(j + 1)) then
t = a(j)
a(j) = a(j + 1)
a(j + 1) = t
swapped = .true.
end if
end do
if (.not. swapped) exit
end do
end subroutine bubble
end module bubbles
program s1
use bubbles
implicit none
integer :: messy(6) = [5, 1, 4, 2, 8, 3]
integer :: tidy(6) = [1, 2, 3, 4, 5, 6]
integer :: p, c
call bubble(messy, p, c)
print '(a, 6(i0, 1x))', 'sorted: ', messy
print '(a, i0, a, i0)', 'passes: ', p, ', comparisons ', c
call bubble(tidy, p, c)
print '(a, 6(i0, 1x))', 'already tidy: ', tidy
print '(a, i0, a, i0)', 'passes: ', p, ', comparisons ', c
end program s1
The six unsorted values need four passes and fourteen comparisons, one fewer than the fifteen of the full quadratic bound, because the fourth pass compared only two pairs, found nothing to swap and stopped. The sorted array needs one pass and five comparisons, which is the best case of the early exit. Bubble sort is stable, since equal neighbours are never swapped, but its quadratic cost keeps it out of real programs; it survives as a teaching example and as a check that a small array is already ordered.
$ gfortran s1.f90 -o s1 $ ./s1 sorted: 1 2 3 4 5 8 passes: 4, comparisons 14 already tidy: 1 2 3 4 5 6 passes: 1, comparisons 5
Insertion sort
Insertion sort grows a sorted prefix from left to right. It takes the next value, shifts the larger values of the prefix one position to the right, and inserts the value into the gap. Shifting is cheaper than swapping because it moves each element once instead of twice, and the algorithm is fast on arrays that are already nearly sorted. The loop that looks for the insertion point tests two conditions, and the way it is written matters.
module insertions
implicit none
private
public :: insertion
contains
subroutine insertion(a, shifts)
integer, intent(inout) :: a(:)
integer, intent(out) :: shifts
integer :: i, j, key
shifts = 0
do i = 2, size(a)
key = a(i)
j = i - 1
do while (j >= 1)
if (a(j) <= key) exit
a(j + 1) = a(j)
j = j - 1
shifts = shifts + 1
end do
a(j + 1) = key
end do
end subroutine insertion
end module insertions
program s2
use insertions
implicit none
integer :: a(8) = [7, 3, 9, 1, 5, 2, 8, 4]
integer :: s
call insertion(a, s)
print '(a, 8(i0, 1x))', 'sorted: ', a
print '(a, i0)', 'shifts: ', s
call insertion(a, s)
print '(a, i0)', 'shifts on sorted input: ', s
end program s2
Eight shuffled values need fifteen shifts, and the same array sorted again
needs none. The loop is written as do while (j >= 1) with a
separate if (a(j) <= key) exit, not as one condition joined with
.and.. Fortran does not require the operands of .and.
to be evaluated left to right with a stop after the first false one; gfortran
evaluates both, so a combined test would read a(0) when
j reaches zero and the bounds check would stop the program. This
is one of the few places where the short form is not just a style choice.
$ gfortran s2.f90 -o s2 $ ./s2 sorted: 1 2 3 4 5 7 8 9 shifts: 15 shifts on sorted input: 0
Selection sort
Selection sort finds the smallest remaining value and swaps it into the next
position of the sorted prefix. It always scans the whole unsorted part, so its
number of comparisons is fixed at about n**2 / 2 whatever the
input, but it performs at most n - 1 swaps. That trade makes it
attractive when moving an element is expensive and comparing two is cheap, for
example when the array holds large records.
module selections
implicit none
private
public :: selection
contains
subroutine selection(a, swaps)
integer, intent(inout) :: a(:)
integer, intent(out) :: swaps
integer :: i, j, best, t
swaps = 0
do i = 1, size(a) - 1
best = i
do j = i + 1, size(a)
if (a(j) < a(best)) best = j
end do
if (best /= i) then
t = a(i)
a(i) = a(best)
a(best) = t
swaps = swaps + 1
end if
end do
end subroutine selection
end module selections
program s3
use selections
implicit none
integer :: a(7) = [64, 25, 12, 22, 11, 90, 11]
integer :: s
call selection(a, s)
print '(a, 7(i0, 1x))', 'sorted: ', a
print '(a, i0)', 'swaps: ', s
end program s3
Seven values with one duplicate are sorted with four swaps, because three of the positions already held their final value. Selection sort is not stable in general: a swap can carry a later element over an earlier one that compares equal, and the reverse order then survives to the end. The two 11s in this example happen to keep their order, but the algorithm offers no guarantee. When stability matters, insertion or merge sort is the better choice.
$ gfortran s3.f90 -o s3 $ ./s3 sorted: 11 11 12 22 25 64 90 swaps: 4
Merge sort
Merge sort divides the array into two halves, sorts each half by calling itself, and merges the two sorted halves into one. The recursion stops when a range holds one element or none. The merge needs a second array of the same size, because writing into the original array while reading from both halves would overwrite values that have not been copied yet; the program allocates one scratch array and passes it down to every call.
module merges
implicit none
private
public :: merge_sort
contains
subroutine merge_sort(a)
integer, intent(inout) :: a(:)
integer, allocatable :: tmp(:)
allocate (tmp(size(a)))
call msort(a, tmp, 1, size(a))
end subroutine merge_sort
recursive subroutine msort(a, tmp, lo, hi)
integer, intent(inout) :: a(:), tmp(:)
integer, intent(in) :: lo, hi
integer :: mid
if (lo >= hi) return
mid = (lo + hi) / 2
call msort(a, tmp, lo, mid)
call msort(a, tmp, mid + 1, hi)
call merge(a, tmp, lo, mid, hi)
end subroutine msort
subroutine merge(a, tmp, lo, mid, hi)
integer, intent(inout) :: a(:), tmp(:)
integer, intent(in) :: lo, mid, hi
integer :: i, j, k
i = lo
j = mid + 1
k = lo
do while (i <= mid .and. j <= hi)
if (a(i) <= a(j)) then
tmp(k) = a(i)
i = i + 1
else
tmp(k) = a(j)
j = j + 1
end if
k = k + 1
end do
if (i <= mid) tmp(k:hi) = a(i:mid)
if (j <= hi) tmp(k:hi) = a(j:hi)
a(lo:hi) = tmp(lo:hi)
end subroutine merge
end module merges
program s4
use merges
implicit none
integer :: a(10) = [38, 27, 43, 3, 9, 82, 10, 1, 55, 27]
call merge_sort(a)
print '(a, 10(i0, 1x))', 'sorted: ', a
end program s4
The ten values, including the duplicate 27, come out in order. The merge takes
the smaller front element of the two halves at every step and copies whatever
remains when one half is exhausted, so the result is sorted and the relative
order of equal values is preserved. Merge sort needs time proportional to
n * log(n) in every case, which makes it the safe choice when the
input might be adversarial, and its one weakness is the extra array.
$ gfortran s4.f90 -o s4 $ ./s4 sorted: 1 3 9 10 27 27 38 43 55 82
Quick sort
Quick sort picks a pivot value, moves every smaller element to its left and every larger element to its right, and then sorts the two sides. The version below chooses the middle element as the pivot, which avoids the worst case for input that is already sorted, and it partitions in place with two indexes that walk towards each other. After the partition, the two sides are sorted by recursive calls on array sections.
module quicks
implicit none
private
public :: quick_sort
contains
recursive subroutine quick_sort(a)
integer, intent(inout) :: a(:)
integer :: pivot, i, j, t
if (size(a) <= 1) return
pivot = a(size(a) / 2 + 1)
i = 1
j = size(a)
do
do while (a(i) < pivot)
i = i + 1
end do
do while (a(j) > pivot)
j = j - 1
end do
if (i <= j) then
t = a(i)
a(i) = a(j)
a(j) = t
i = i + 1
j = j - 1
end if
if (i > j) exit
end do
if (j > 1) call quick_sort(a(1:j))
if (i < size(a)) call quick_sort(a(i:))
end subroutine quick_sort
end module quicks
program s5
use quicks
implicit none
integer :: a(10) = [38, 27, 43, 3, 9, 82, 10, 1, 55, 27]
integer :: b(6) = [9, 8, 7, 6, 5, 4]
call quick_sort(a)
print '(a, 10(i0, 1x))', 'random order: ', a
call quick_sort(b)
print '(a, 6(i0, 1x))', 'reversed: ', b
end program s5
Both the shuffled array and the reversed one are sorted correctly. Quick sort
is the fastest of the five in practice, because its inner loops touch memory in
order and it needs no scratch array, but its worst case is still quadratic: a
pivot that always splits the array into one empty side and one full side gives
n levels of recursion. Choosing the middle element, or the median
of three, makes that case unlikely without changing the code by much.
$ gfortran s5.f90 -o s5 $ ./s5 random order: 1 3 9 10 27 27 38 43 55 82 reversed: 4 5 6 7 8 9
Sorting records by a key
Arrays of numbers are the easy case. A program usually sorts records by one
field, and it may need two different orders for the same record type. The
insertion sort below takes a comparison procedure as an argument: a
function that receives two records and says whether the first must come before
the second. The caller supplies by_age or by_name, and
the sorting code itself never looks at a component.
module people
implicit none
private
public :: person, by_age, by_name, sort_people
type :: person
character(len=10) :: name = ''
integer :: age = 0
end type person
abstract interface
logical function compare_iface(x, y)
import :: person
type(person), intent(in) :: x, y
end function compare_iface
end interface
contains
pure logical function by_age(x, y) result(r)
type(person), intent(in) :: x, y
r = x%age < y%age
end function by_age
pure logical function by_name(x, y) result(r)
type(person), intent(in) :: x, y
r = x%name < y%name
end function by_name
subroutine sort_people(a, before)
type(person), intent(inout) :: a(:)
procedure(compare_iface) :: before
type(person) :: key
integer :: i, j
do i = 2, size(a)
key = a(i)
j = i - 1
do while (j >= 1)
if (.not. before(key, a(j))) exit
a(j + 1) = a(j)
j = j - 1
end do
a(j + 1) = key
end do
end subroutine sort_people
end module people
program s6
use people
implicit none
type(person) :: group(5) = [ &
person('carol', 34), person('alice', 28), person('dave', 45), &
person('bob', 28), person('erin', 31)]
integer :: i
call sort_people(group, by_age)
print *, 'by age:'
do i = 1, size(group)
print '(a, a, a, i0)', ' ', trim(group(i)%name), ' ', group(i)%age
end do
call sort_people(group, by_name)
print *, 'by name:'
do i = 1, size(group)
print '(a, a, a, i0)', ' ', trim(group(i)%name), ' ', group(i)%age
end do
end program s6
Sorting by age puts alice and bob, both 28, first and keeps alice before bob,
because the algorithm inserts a value after every equal one that it meets. The
second call reorders the same array alphabetically, and the ages travel with
the names. The argument before is declared with
procedure(compare_iface), where compare_iface is an
abstract interface declared in the module; the full rules for such arguments
are the subject of the procedure arguments article.
$ gfortran s6.f90 -o s6 $ ./s6 by age: alice 28 bob 28 erin 31 carol 34 dave 45 by name: alice 28 bob 28 carol 34 dave 45 erin 31
Sorting an index array
Sometimes the data must not move at all: it may be shared with other parts of
the program, or the records may be too large to copy. The alternative is to
sort an array of positions. The array order starts as
[1, 2, 3, ...], and the sort compares the values that each position
points to, so it permutes the indexes and leaves the data untouched. This is
often called an argsort, and it is the same comparison that a lookup
table would use.
program s7
implicit none
character(len=8) :: names(6)
integer :: score(6), order(6)
integer :: i, j, t
names = [character(len=8) :: 'carol', 'alice', 'dave', 'bob', &
'erin', 'frank']
score = [82, 95, 71, 88, 95, 60]
order = [(i, i = 1, size(score))]
do i = 2, size(order)
t = order(i)
j = i - 1
do while (j >= 1)
if (score(order(j)) > score(t)) exit
if (score(order(j)) == score(t) .and. &
names(order(j)) <= names(t)) exit
order(j + 1) = order(j)
j = j - 1
end do
order(j + 1) = t
end do
print *, 'ranking:'
do i = 1, size(order)
print '(a, i0, a, a, a, i0)', ' ', i, '. ', &
trim(names(order(i))), ' ', score(order(i))
end do
end program s7
The ranking puts the two scores of 95 first, with alice before erin because the
tie is broken by name, then bob, carol, dave and frank. Nothing was copied: the
names and scores stayed in their original positions, and only order
changed. The same trick gives a stable result on data that must keep its
original lay out, and reading names(order(i)) gives the sorted
sequence whenever it is needed.
$ gfortran s7.f90 -o s7 $ ./s7 ranking: 1. alice 95 2. erin 95 3. bob 88 4. carol 82 5. dave 71 6. frank 60
Next steps
The searching article uses a sorted array for binary search and compares its cost with a linear scan and a hash table. The recursion article explains the mechanics of the merge and quick sorts, and the procedure arguments and callbacks article covers the interface block that the record sort uses. The arrays article explains array sections, which quick sort passes to its recursive calls, and the array intrinsics article shows the operations that a loop over a sorted array can be replaced with.
Source
Fortran 2018 standard (J3/18-007r1)
Fortran-lang: learning resources
In this article we have sorted arrays with bubble, insertion, selection, merge and quick sort, counted the passes, shifts and swaps that each one performed, sorted an array of records by two different keys with a comparison procedure, and reordered an index array to rank data without moving it. The previous article, Fortran recursion, explains the recursive calls inside merge and quick sort.
Author
List all Fortran tutorials.