Diomidis Spinellis blog ## How to Sort Three Numbers

Quick: how do you sort three numbers in ascending order?

Here is an excerpt from the first page returned by Google.

```! -------------------------------------------------------
! This program reads in three INTEGERs and displays them
! in ascending order.
! -------------------------------------------------------

PROGRAM  Order
IMPLICIT  NONE

INTEGER  :: a, b, c

IF (a < b) THEN                 ! a < b here
IF (a < c) THEN              !   a < c     : a the smallest
IF (b < c) THEN           !      b < c  : a < b < c
WRITE(*,*)  a, b, c
ELSE                      !      c <= b : a < c <= b
WRITE(*,*)  a, c, b
END IF
ELSE                         !   a >= c    : c <= a < b
WRITE(*,*) c, a, b
END IF
ELSE                            ! b <= a here
IF (b < c) THEN              !   b < c     : b the smallest
IF (a < c) THEN           !     a < c   : b <= a < c
WRITE(*,*)  b, a, c
ELSE                      !     a >= c  : b < c <= a
WRITE(*,*)  b, c, a
END IF
ELSE                         !   c <= b    : c <= b <= a
WRITE(*,*)  c, b, a
END IF
END IF

END PROGRAM  Order
```
Ouch! Can we do better? Sure, look at this:
```int a, b, c;

#define swap(x, y) do {int tmp; tmp = x; x = y; y = tmp; } while (0)

if (b < a) swap(b, a);
if (c < b) swap(c, b);
if (b < a) swap(b, a);
```
How about sorting four numbers? Here is the solution:
```if (b < a) swap(b, a);
if (c < b) swap(c, b);
if (d < c) swap(d, c);
if (b < a) swap(b, a);
if (c < b) swap(c, b);
if (b < a) swap(b, a);
```
The above code is probably at the limit of being inefficient; for more numbers we should call a sorting function, like the C library's qsort().

Nevertheless, there's still one more question: How do we come up with the above solutions, and how do we know they are correct?

The answer is also simple, and it is called abstract interepretation. We simply write a program that performs the bubble sort algorithm (this is how the above code snippets work), but we substitute the loop's innermost statement with a print statement. Here is the code:

```main()
{
int i, j;
const int n = 4;

for (i = 0; i < n - 1; i++)
for (j = 0; j < n - 1 - i; j++)
printf("if (%c < %c) swap(%c, %c);\n",
'a' + j + 1, 'a' + j, 'a' + j + 1, 'a' + j);
}
```