Capstone 3: sorting the records
Fortran has no sort in its standard library. There is no SORT intrinsic next to SUM and MATMUL, no generic in a module that ships with the compiler, and the language has never had one. Every Fortran project that needs records in order writes a sort, and most write the same forty lines. This lesson writes them over the record type of the previous one, sorts by date and then by region, and checks the result rather than trusting it.
No sort intrinsic
The intrinsics of part 5 of the course cover the reductions, the searching of MAXLOC and FINDLOC and the reshaping of PACK and RESHAPE, and none of them reorders an array. Lesson 044 sorted numbers with a bubble sort and with a selection sort built on MAXLOC; both are quadratic and both are easy to read. The record batch needs a comparison on two fields and a sort that keeps equal keys in file order, and an insertion sort gives both in one procedure.
The comparison function
BEFORE(A, B) answers one question: does record A belong before record B? It compares the dates first, and when the dates are equal it compares the regions. Writing the order as one PURE function is what makes the sort short: the sort never looks at the fields, so changing the order of the report is a change to this function and nothing else.
The dates are YYYY-MM-DD strings, which sort correctly as text because the year comes first and every field has a fixed width. That is not an accident of this file: it is the reason the ISO date format exists, and a batch that has dates as DD/MM/YYYY needs either a parse into three integers or a conversion before it can compare them.
The string comparison is the < operator on characters, which compares the collating sequence: for the lower-case letters of these regions it is the alphabetical order, and for mixed case or accented text it may not be what a reader expects. A batch that sorts names compares with LLE and LGT, or normalises the case first.
Insertion sort
The sort walks the array once, takes each element as a key, and moves it left over the elements that belong after it. It is stable, because an element only moves past one that is strictly before it, and it is quadratic in the worst case, because an element may move past the whole prefix. For twelve records that is invisible; for a million it is minutes, and the section on larger files says what to do instead.
The inner loop is a DO WHILE with EXIT rather than a DO with a computed bound, because the bound is the answer the loop is looking for. The key is copied into a temporary record before the shifting starts, which is what makes the move a rotation and not a swap.
The check
IS_SORTED walks the array once and answers whether every record belongs after the one before it. It is the same predicate the sort is built on, used backwards, and it costs nothing at this size. A program that sorts and then prints does not prove that it sorted; a program that prints a T from this function does, for the data it was given.
The run
The file sort.f90 is the module of lesson 132 with the comparison, the sort and the check added, and a program that prints the records twice:
module records
use, intrinsic :: iso_fortran_env, only: dp => real64
implicit none
private
public :: record, load, write_sample, before, sort_records, is_sorted
integer, parameter :: date_len = 10, region_len = 8
type :: record
character(len=date_len) :: date = ' '
character(len=region_len) :: region = ' '
real(dp) :: amount = 0.0_dp
end type record
contains
subroutine write_sample(path)
character(len=*), intent(in) :: path
integer :: u
open (newunit=u, file=path, status='replace', action='write')
write (u, '(a)') '2026-03-02,east,3050.00'
write (u, '(a)') '2026-01-11,south,980.00'
write (u, '(a)') '2026-02-16,north,1890.00'
write (u, '(a)') '2026-01-04,north,1200.50'
write (u, '(a)') '2026-03-16,south,1425.60'
write (u, '(a)') '2026-02-09,east,540.75'
write (u, '(a)') '2026-01-25,north,760.00'
write (u, '(a)') '2026-02-16,east,410.00'
write (u, '(a)') '2026-01-18,east,1430.25'
write (u, '(a)') '2026-03-09,north,675.25'
write (u, '(a)') '2026-02-23,south,1120.40'
write (u, '(a)') '2026-03-23,east,880.00'
write (u, '(a)') '# a comment line the batch skips'
write (u, '(a)') '2026-03-30,west,oops'
close (u)
end subroutine write_sample
subroutine load(path, recs, n, skipped, n_skipped)
character(len=*), intent(in) :: path
type(record), allocatable, intent(out) :: recs(:)
integer, intent(out) :: n
character(len=80), allocatable, intent(out) :: skipped(:)
integer, intent(out) :: n_skipped
integer :: u, ios, line_no
character(len=120) :: line
type(record) :: r
allocate (recs(8), skipped(8))
n = 0
n_skipped = 0
open (newunit=u, file=path, status='old', action='read', iostat=ios)
if (ios /= 0) error stop 'load: cannot open the file'
line_no = 0
do
read (u, '(a)', iostat=ios) line
if (ios /= 0) exit
line_no = line_no + 1
read (line, *, iostat=ios) r%date, r%region, r%amount
if (ios == 0 .and. len_trim(r%date) == date_len .and. r%amount >= 0.0_dp) then
call append_record(recs, n, r)
else
call append_line(skipped, n_skipped, line)
end if
end do
close (u)
print '(a,a,a,i0,a,i0,a,i0,a)', 'read ', path, ': ', n, ' records, ', n_skipped, ' lines skipped from ', line_no, ' lines'
end subroutine load
pure function before(a, b) result(earlier)
type(record), intent(in) :: a, b
logical :: earlier
if (a%date /= b%date) then
earlier = a%date < b%date
else
earlier = a%region < b%region
end if
end function before
subroutine sort_records(list, n)
type(record), intent(inout) :: list(:)
integer, intent(in) :: n
integer :: i, j
type(record) :: key
do i = 2, n
key = list(i)
j = i - 1
do while (j >= 1)
if (.not. before(key, list(j))) exit
list(j + 1) = list(j)
j = j - 1
end do
list(j + 1) = key
end do
end subroutine sort_records
function is_sorted(list, n) result(ok)
type(record), intent(in) :: list(:)
integer, intent(in) :: n
logical :: ok
integer :: i
ok = .true.
do i = 2, n
if (before(list(i), list(i - 1))) ok = .false.
end do
end function is_sorted
subroutine append_record(list, n, r)
type(record), allocatable, intent(inout) :: list(:)
integer, intent(inout) :: n
type(record), intent(in) :: r
type(record), allocatable :: bigger(:)
if (n == size(list)) then
allocate (bigger(max(8, 2 * n)))
bigger(1:n) = list(1:n)
call move_alloc(bigger, list)
end if
n = n + 1
list(n) = r
end subroutine append_record
subroutine append_line(list, n, line)
character(len=*), allocatable, intent(inout) :: list(:)
integer, intent(inout) :: n
character(len=*), intent(in) :: line
character(len=80), allocatable :: bigger(:)
if (n == size(list)) then
allocate (bigger(max(8, 2 * n)))
bigger(1:n) = list(1:n)
call move_alloc(bigger, list)
end if
n = n + 1
list(n) = line
end subroutine append_line
end module records
program load_demo
use records
implicit none
type(record), allocatable :: recs(:)
character(len=80), allocatable :: skipped(:)
integer :: n, n_skipped
call write_sample('sales.csv')
call load('sales.csv', recs, n, skipped, n_skipped)
print '(a)', 'file order:'
call print_records(recs, n)
print '(a,l1)', 'sorted before the sort = ', is_sorted(recs, n)
call sort_records(recs, n)
print '(a)', 'sorted by date, then region:'
call print_records(recs, n)
print '(a,l1)', 'sorted after the sort = ', is_sorted(recs, n)
contains
subroutine print_records(list, n)
type(record), intent(in) :: list(:)
integer, intent(in) :: n
integer :: i
do i = 1, n
print '(a10,2x,a8,2x,f9.2)', list(i)%date, list(i)%region, list(i)%amount
end do
end subroutine print_records
end program load_demo
gfortran -Wall -Wextra -std=f2018 sort.f90 -o sort
./sort
read sales.csv: 12 records, 2 lines skipped from 14 lines
file order:
2026-03-02 east 3050.00
2026-01-11 south 980.00
2026-02-16 north 1890.00
2026-01-04 north 1200.50
2026-03-16 south 1425.60
2026-02-09 east 540.75
2026-01-25 north 760.00
2026-02-16 east 410.00
2026-01-18 east 1430.25
2026-03-09 north 675.25
2026-02-23 south 1120.40
2026-03-23 east 880.00
sorted before the sort = F
sorted by date, then region:
2026-01-04 north 1200.50
2026-01-11 south 980.00
2026-01-18 east 1430.25
2026-01-25 north 760.00
2026-02-09 east 540.75
2026-02-16 east 410.00
2026-02-16 north 1890.00
2026-02-23 south 1120.40
2026-03-02 east 3050.00
2026-03-09 north 675.25
2026-03-16 south 1425.60
2026-03-23 east 880.00
sorted after the sort = T
The file order starts with March and mixes the months, and the check on it prints sorted before the sort = F. After the sort the dates run from January to March, the two records of 2026-02-16 arrive together with east before north, and the check prints T. The two records that shared a date kept their relative order from the file, which is the stability of the insertion sort showing in the output.
A larger file
Insertion sort is the right choice up to a few thousand records. Beyond that, three routes are open, and all of them are a page each in a library that this capstone does not have. A merge sort is stable, O(n log n) and about sixty lines, and it is what most Fortran projects write. A sorted index array, built with the same insertion sort over INTEGER indices, keeps the records in file order and sorts only the pointers to them, which is what a table of contents does. And an external sort that writes runs to a file and merges them is the answer when the data does not fit in memory, which is the case a Fortran batch meets more often than a web program does.
Whatever the algorithm, the comparison function stays: a merge sort over this type calls BEFORE in the same way, so the report of the next lesson does not have to know which sort produced the order.
The report
With the records in order, the report is a walk over the array that starts a new group when the month changes and adds a total. The next lesson writes it: a header, one line per record with the amount, a subtotal per month, a grand total, and the count that proves no record was lost between the file and the table.
Exercises
- Sort by amount, largest first. Which line of BEFORE changes, and what happens to two records with the same amount?
- Replace the insertion sort with the selection sort of lesson 044 and sort this file. Does the order of the two 2026-02-16 records change?
- Sort an index array instead of the records. Which two procedures change, and which one does not?
- Time the sort on a file of 100000 generated records. How long does it take, and where does the time go?
Questions
A new set of questions in a new order every time. Choose one answer for each, then check.
-
Which intrinsic sorts an array?
Answer
None: Fortran has no sort in its standard library
Every project writes its own.
-
What does BEFORE compare first?
Answer
The date, then the region when the dates are equal
One pure function holds the order.
-
Why do YYYY-MM-DD dates sort as text?
Answer
The year comes first and every field has a fixed width
That is why the format exists.
-
Why is insertion sort stable here?
Answer
An element only moves past one that is strictly before it
Equal keys keep their order.
-
What is the worst case of insertion sort?
Answer
Quadratic in the number of records
A reversed array moves every element the whole way.
-
What did the check print before the sort?
Answer
F
The file starts with March.
-
Which two records share a date?
Answer
2026-02-16 east and 2026-02-16 north
The second key decides their order.
-
What does IS_SORTED do?
Answer
Walks the array and checks that every record belongs after the one before
A sort that prints does not prove it sorted.
-
What replaces insertion sort for a million records?
Answer
A merge sort, or a sorted index array
Quadratic is minutes at that size.
-
What stays the same if the algorithm changes?
Answer
The comparison function
The order is a property of BEFORE.
The programs on this page were built with GNU Fortran (Alpine 15.2.0) 15.2.0 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container.
Article author: Arthur Isaev