[Back to the 30 Days of Programming Overview Page]

## Insertion Sort in INTERCAL

Oh dear god, INTERCAL. This language is insane. This actually took me three days. I managed to figure out how to do comparison, branching, and looping, though, and once I got those down, things got a lot easier. That's not saying much, though. Anyway, below is the INTERCAL code (with the PLEASEs removed because, while they are a hilarious part of the spec, they aren't terribly interesting as part of the code), and then below that is roughly directly translated Python code, to give a slightly better idea of what's going on.

You can download everything (the code, the translated Python code, a Makefile, and a Python script to add PLEASEs) in a zip file (02.zip).

### INTERCAL (insertion.i)

DO NOTE: vim: set ft=intercal :
DO NOTE: Array length less than 2 is not checked but is an error
DO NOTE: Variables:
DO NOTE: ,1: Array
DO NOTE: .1: Increment scratch
DO NOTE: .2: Operand scratch
DO NOTE: .3: Result scratch
DO NOTE: .4: Overflow scratch
DO NOTE: .5: Array length
DO NOTE: .6: Iteration variable
DO NOTE: .7: Current array element
DO NOTE: .8: Another iteration variable
DO NOTE: .9: Another array element
DO NOTE: First, we read the length of the array
DO WRITE IN .5
DO ,1 <- .5
DO NOTE: Now we need to read in the values of the array
DO .6 <- #1
(1) DO FORGET #1
DO WRITE IN ,1 SUB .6
DO NOTE: Checking and Increment
DO (101) NEXT
DO (110) NEXT
DO NOTE: Branching
DO (2) NEXT
DO NOTE: Only get here if Length > Index we just read into
DO (1) NEXT
(2) DO (3) NEXT
DO NOTE: Only get here if Length <= Index we just read into
DO (4) NEXT
(3) DO RESUME .4
(4) DO FORGET #2
DO NOTE: Now we can start the insertion sort
DO .6 <- #2
(5) DO FORGET #1
DO .7 <- ,1 SUB .6
DO .8 <- .6
DO (120) NEXT
DO NOTE: Nested loop
(6) DO FORGET #1
DO .9 <- ,1 SUB .8
DO NOTE: Check if .9 > .7
DO (102) NEXT
DO (12) NEXT
DO NOTE: Only get here if .9 > .7: Do loop body
DO (7) NEXT
(12) DO (13) NEXT
DO NOTE: Only get here if .9 <= .7: Break
DO (8) NEXT
(13) DO RESUME .4
(7) DO FORGET #1
DO .1 <- .8
DO (1020) NEXT
DO ,1 SUB .1 <- ,1 SUB .8
DO (120) NEXT
DO NOTE: Check if .8 > 0
DO .1 <- .8
DO .2 <- #65535
DO (1009) NEXT
DO NOTE: Now .4 <- #2 if .8 > 0 else #1
DO (22) NEXT
DO NOTE: Only get here if .8 > 0
DO (6) NEXT
(22) DO (23) NEXT
DO NOTE: Only get here if .8 == 0
DO (8) NEXT
(23) DO RESUME .4
DO NOTE: End of nested loop
(8) DO FORGET #2
DO NOTE: Place current element
DO .1 <- .8
DO (1020) NEXT
DO ,1 SUB .1 <- .7
DO NOTE: Checking and Increment
DO (101) NEXT
DO (110) NEXT
DO NOTE: Branching
DO (32) NEXT
DO NOTE: Only get here if Length > Index we just processed
DO (5) NEXT
(32) DO (33) NEXT
DO NOTE: Only get here if Length <= Index we just processed
DO (34) NEXT
(33) DO RESUME .4
(34) DO FORGET #2
DO NOTE: Now we can output the result array
DO .6 <- #1
(41) DO FORGET #1
DO READ OUT ,1 SUB .6
DO NOTE: Checking and Increment
DO (101) NEXT
DO (110) NEXT
DO NOTE: Branching
DO (42) NEXT
DO NOTE: Only get here if Length > Index we just wrote out of
DO (41) NEXT
(42) DO (43) NEXT
DO NOTE: Only get here if Length <= Index we just wrote out of
DO GIVE UP
(43) DO RESUME .4
DO NOTE: The remainder of the file is subroutines
DO NOTE: Subroutine: .4 <- #2 if .2 > .1 else #1 (Writes .1 through .4)
DO NOTE: Underflow subtraction and then detect overflow on addition
(100) DO (1010) NEXT
DO .1 <- .3
DO (1009) NEXT
DO RESUME #1
DO NOTE: Subroutine: .4 <- #2 if .5 > .6 else #1 (Writes .1 through .4)
(101) DO .1 <- .6
DO .2 <- .5
DO (100) NEXT
DO RESUME #1
DO NOTE: Subroutine: .4 <- #2 if .9 > .7 else #1 (Writes .1 through .4)
(102) DO .1 <- .7
DO .2 <- .9
DO (100) NEXT
DO RESUME #1
DO NOTE: Subroutine: Increment .6 (Writes .1)
(110) DO .1 <- .6
DO (1020) NEXT
DO .6 <- .1
DO RESUME #1
DO NOTE: Subroutine: Decrement .8 (Writes .1 through .3)
(120) DO .1 <- .8
DO .2 <- #1
DO (1010) NEXT
DO .8 <- .3
DO RESUME #1



### Python (insertion.py)

#!/usr/bin/env python3
# Array length less than 2 is not checked but is an error
# First, we read the length of the array
length = int(input())               # WRITE IN .5
# INTERCAL arrays are 1-indexed: simulating that with None at index 0
arr = [None] + [None] * length      # ,1 <- .5
# Now we need to read in the values of the array
i = 1                               # .6 <- #1
while True:                         # label (1)
arr[i] = int(input())           # WRITE IN ,1 SUB .6
# Checking and Increment
gt = (length > i)               # (101) NEXT
i += 1                          # (110) NEXT
# Branching
if gt:
# Only get here if Length > Index we just read into
continue                    # (1) NEXT
else:
# Only get here if Length <= Index we just read into
break                       # (4) NEXT
# Now we can start the insertion sort
i = 2                               # .6 <- #2
while True:                         # label (5)
x = arr[i]                      # .7 <- ,1 SUB .6
j = i - 1                       # .8 <- .6; (120) NEXT
# Nested loop
while True:                     # label (6)
y = arr[j]                  # .9 <- ,1 SUB .8
# Check if y > x
gt = (y > x)                # (102) NEXT
if gt:
# Only get here if y > x: Do loop body
pass                    # (7) NEXT
else:
# Only get here if x <= y: Break
break                   # (8) NEXT
arr[j + 1] = arr[j]         # .1 <- .8; (1020) NEXT; ,1 SUB .1 <- ,1 SUB .8
j -= 1                      # (120) NEXT
# Check if j > 0
gt = (j > 0)                # .1 <- .8; .2 <- #65535; (1009) NEXT
# Now gt = True if j > 0 else False
if gt:
# Only get here if j > 0
continue                # (6) NEXT
else:
# Only get here if j == 0
break                   # (8) NEXT
# End of nested loop
# Place current element
arr[j + 1] = x                  # .1 <- .8; (1020) NEXT; ,1 SUB .1 <- .7
# Checking and Increment
gt = (length > i)               # (101) NEXT
i += 1                          # (110) NEXT
# Branching
if gt:
# Only get here if Length > Index we just processed
continue                    # (5) NEXT
else:
# Only get here if Length <= Index we just processed
break                       # (34) NEXT
i = 1 # .6 <- #1
while True:                         # label (41)
print('\n{}'.format(arr[i]))    # READ OUT ,1 SUB .6
# Checking and Increment
gt = (length > i)               # (101) NEXT
i += 1                          # (110) NEXT
# Branching
if gt:
# Only get here if Length > Index we just wrote out of
continue                    # (41) NEXT
else:
# Only get here if Length <= Index we just wrote out of
raise SystemExit(0)         # GIVE UP