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

  1. Sort by amount, largest first. Which line of BEFORE changes, and what happens to two records with the same amount?
  2. 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?
  3. Sort an index array instead of the records. Which two procedures change, and which one does not?
  4. 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.

  1. Which intrinsic sorts an array?

    Answer

    None: Fortran has no sort in its standard library

    Every project writes its own.

  2. What does BEFORE compare first?

    Answer

    The date, then the region when the dates are equal

    One pure function holds the order.

  3. 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.

  4. Why is insertion sort stable here?

    Answer

    An element only moves past one that is strictly before it

    Equal keys keep their order.

  5. What is the worst case of insertion sort?

    Answer

    Quadratic in the number of records

    A reversed array moves every element the whole way.

  6. What did the check print before the sort?

    Answer

    F

    The file starts with March.

  7. Which two records share a date?

    Answer

    2026-02-16 east and 2026-02-16 north

    The second key decides their order.

  8. 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.

  9. What replaces insertion sort for a million records?

    Answer

    A merge sort, or a sorted index array

    Quadratic is minutes at that size.

  10. 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