Merge sort (dc)

From LiteratePrograms

Other implementations: ACL2 | C | C++ | dc | Eiffel | Erlang | Haskell | Java | JavaScript | Lisp | OCaml | Oz | Perl | Prolog | Python | Ruby | Scheme

Contents 1 theory 2 practice 2.1 dataflow 2.2 merge sort 2.3 choose element 2.4 data representation 3 wrapping up

theory

Most sorting algorithms rely upon random-access memory, but merge sort is interesting because it is effective even when one has an extremely restrictive interface to the store (such as an external tape drive or an internal linked-list).

The primary data type in dc is the arbitrary-precision number. With one such number we have a stack, accessed via the units position; with two such numbers, mirrored with respect to each other, we have a structure resembling a tape.

Given the sequential-access nature of dc numeric values, the merge sort would appear to be a natural algorithm for this environment.

practice

dataflow

With a only few exceptions, dc identifiers are limited to single characters. We will follow a "harvard" convention, and use the lower-case registers for varying values, retaining the upper-case for constant code. Here is a quick synopsis of the program state:

The primary variable is s, containing the list to be sorted. It is split into pairs of lists, x and y (of stride length l). Each of these is split into elements, g and h respectively, and merged onto a result list z. Finally, to set up the next pass, the data from z is rewound onto s, and l is doubled to match the new stride length.

merge sort

Merge sort is traditionally presented as a top-down recursive process, dividing lists into sublists and merging the sublists to return sorted lists.

msort xs = merge (msort as) (msort zs), where as ++ zs = xs

Here, we choose to proceed from the bottom-up. By allowing us to dispense with both the control stack and the initial splitting phase, we can cut directly to an iterative merging phase. We merge strides of length 1 to produce sorted runs of length 2, then stride by 2 to produce runs of 4, etc.

FOREACH stride length in 1,2,4,8,...:
 FOREACH pair of strides in the input:
  MERGE the pairs to produce a run of twice the stride length

The actual code has a little more ancillary detail. A complete pass

1. partitions and merges by stride (lPx)
2. rewinds (lRx) the merged output back to the input
3. doubles the stride length (ll 2* sl)
4. and repeats while the input is longer than a stride (ll lsZ >D).

(to animate the algorithm, insert lspd at the start)

<<double stride length>>=
[lPx lRx ll 2* sl ll lsZ >D]sD

To perform a merge pass, we

1. pull a stride into each of the x and y registers (lSx sx, resp. sy)
2. pull an element from each stride into the g and h registers (lXx sg, resp. lYx sh)
3. which primes the merge (lMx)
4. and repeat while we have input (ls 0<P).

<<partition into strides>>=
[lSxsx lSxsy lXxsg lYxsh lMx ls0<P]sP

The merge itself consists of

1. choosing elements to shift onto the output (lCx)
2. and repeating while data is present in either of the g or h registers (lg lh + 0<M).

<<merge stride pair>>=
[lCx lglh+ 0<M]sM

choose element

To choose a maximal element to merge, we compare g and h. If g (resp. h) dominates, we write its value to the output z (lZx) and read a new value from x (resp. y).

(q is a little like "^" in smalltalk, in that it terminates two stack levels: the current macro and its caller. This behavior may seem odd, but it is convenient, as here, when synthesizing case analyses)

<<choose element>>=
[lg lZx lXx sg q]sG
[lh lZx lYx sh q]sH
[lglh<G lglh!<H]sC

data representation

Slogan: "integers are lists"

• In order to pop X, pop Y, and push Z, we work an element at a time, where B = 10.
• We pop S by stride, so we must use B = 10^l instead.
• To Rewind, we repeatedly pop from z (lz10~rsz) and push onto s (ls10*+ss) until z is empty (lz0<R).

<<data representation>>=
[lx 10 ~r sx]sX
[ly 10 ~r sy]sY
[lz 10 *+ sz]sZ
[ls 10 ll ^ ~r ss]sS
[lz 10 ~r sz ls 10 *+ ss lz0<R]sR

wrapping up

All that remains is a little cryptic code to:

1. print some instructions ([Sort the nonzero digits of a number:newline]P)
2. then invoke the Toplevel REPL (lTx), which
   1. sets a known state (c 0sz 1sl)
   2. prompts for and reads an input ([? ]P ? z0!=U), and the continuation U
   3. evaluates msort(input) (ss lDx)
   4. pretty-prints the output ([= ]P lsp)
   5. and repeats indefinitely (lTx).

<<repl>>=
[c0sz1sl[? ]P?z0!=U]sT
[sslDx[= ]PlsplTx]sU
[Sort the nonzero digits of a number:
]PlTx

(the restriction to nonzero digits may seem strict, but entering data with leading zeros is not so easy)

<<mergesort.dc>>=
#!/usr/bin/dc
data representation
choose element
merge sort
repl
<<merge sort>>=
merge stride pair
partition into strides
double stride length

Download code