Machine.java

import java.util.List;
import java.util.Arrays;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Formatter;

public class Machine {
    private Tape<Integer>[] tapes;
    private int[] memory;
    private final int scratch;          // index of the scratch tape
    private final int reserved = 16;    // Words reserved for internal operation
                                        // (everything else is volatile sorting space)

    public Machine(int tapes, int size) {
        this.tapes = new Tape[tapes];
        this.memory = new int[size];

        for (int i = 0; i < tapes; i++) {
            this.tapes[i] = new Tape<Integer>();
        }

        scratch = this.tapes.length - 1;
    }

    public Machine(int tapes, int size, Integer... input) {
        this(tapes, size);
        this.tapes[0] = new Tape<Integer>(Arrays.asList(input));
    }

    /**
     * Sorts the contents of the 0th tape.
     *
     * @return Pointer to the tape that contains the sorted data.
     */
    public Tape<Integer> sort() {
        final Tape<Integer> input = tapes[0];

        memory[0] = reserved; // i
        memory[1] = 0; // total length
        memory[2] = memory.length - reserved; // size of merge round
        memory[3] = 1; // current round's `input` tape
        memory[4] = 2; // current round's `output` tape

        while (null != input.get()) {
            memory[memory[0]] = input.get();
            memory[1]++;
            memory[0]++;
            input.advance();
            if (memory[0] == memory.length) {
                memory_sort();
                dump_to_tape(tapes[memory[3]]);
            }
        }

        if (memory[0] != reserved) {
            memory_sort();
            dump_to_tape(tapes[memory[3]]);
        }

        while(memory[2] < memory[1]) {
            tapes[memory[3]].rewind();
            tapes[memory[4]].rewind();

            for (memory[0] = 0; memory[0] < memory[1]/(memory[2] * 2)+1; memory[0]++) {
                tapes[scratch].rewind();
                copy_n_from_to(tapes[memory[3]], tapes[scratch]);
                tapes[scratch].rewind();
                merge(tapes[memory[3]], tapes[scratch], tapes[memory[4]]);
            }
            memory[2] *= 2;
            swap(3,4);
        }

        return tapes[memory[3]];
    }

    /**
     * In-place sort the contents of the volatile memory store. Implementation
     * is a heap sort - O(N * log(N)) time complexity, O(1) space complexity.
     */
    private void memory_sort() {
        heap(reserved,memory[0] - reserved);
        memory[5] = (memory[0] - reserved) - 1;
        while (memory[5] > 0) {
            swap(reserved + memory[5], reserved);
            memory[5]--;
            sift(reserved, 0, memory[5]);
        }
    }

    /**
     * Heapify a chunk of memory.
     *
     * @param array     The start address of the heap.
     * @param length    The size of the heap.
     */
    private void heap(int array, int length) {
        memory[6] = (length - 2) / 2;
        while (memory[6] >= 0) {
            sift(array, memory[6], length - 1);
            memory[6]--;
        }
    }

    /**
     * Sift-down operation on an in-memory heap.
     *
     * @param array     The start address of the heap.
     * @param start     The offset from the start address that we're sifting
     *                  down from.
     * @param length    The size of the heap.
     */
    private void sift(int array, int start, int length) {
        memory[7] = start;  // root

        while (memory[7] * 2 + 1 <= length) {
            memory[8] = memory[7] * 2 + 1;  // child
            memory[9] = memory[7];          // swap

            if (memory[array + memory[9]] < memory[array + memory[8]])
                memory[9] = memory[8];
            if (memory[8] + 1 <= length && memory[array + memory[9]] < memory[array + memory[8] + 1])
                memory[9] = memory[8] + 1;

            if (memory[7] != memory[9]) {
                swap(array + memory[7], array + memory[9]);
                memory[7] = memory[9];
            } else {
                return;
            }
        }
    }

    /**
     * Swaps two memory values.
     *
     * @param a     Address of the first value.
     * @param b     Address of the second value.
     */
    private void swap(int a, int b) {
        memory[a] ^= memory[b];
        memory[b] ^= memory[a];
        memory[a] ^= memory[b];
    }

    /**
     * Dumps the current volatile memory store to <code>tape</code>. The read
     * head of <code>tape</code> will be advanced by the number of elements
     * currently being temporarily stored in memory. Uses
     * <code>memory[11]</code>.
     *
     * @param memory[0]     The end of the current volatile memory store. Will
     *                      be reset to <code>reserved</code> when the
     *                      operation is complete.
     */
    private void dump_to_tape(Tape<Integer> tape) {
        memory[10] = reserved;
        while (memory[10] < memory[0]) {
            tape.set(memory[memory[10]++]);
            tape.advance();
        }
        memory[0] = reserved;
    }

    /**
     * Copies <code>n</code> elements from {@link Tape} <code>from</code> to
     * tape <code>to</code>. The read heads of both tapes will be advanced by
     * <code>n</code>. Uses <code>memory[11]</code>.
     *
     * @param memory[2]     The number of elements to copy.
     */
    private void copy_n_from_to(Tape<Integer> from, Tape<Integer> to) {
        memory[11] = memory[2];
        while (memory[11]-- > 0) {
            to.set(from.get());
            from.advance();
            to.advance();
        }
    }

    /**
     * Merge at most <code>n</code> words from {@link Tape}s <code>a</code> and
     * <code>b</code> into <code>Tape</code> <code>to</code>. The read heads of
     * <code>a</code> and <code>b</code> should start at the beginning of both
     * lists of things to merge. Both lists are assumed to be already sorted
     * for at least the first <code>n</code> elements. Lists are assumed to be
     * null-terminated on the tape and the read head is not advanced past the
     * end of the list. The read heads of both tapes are guaranteed to not be
     * advanced <em>more</em> than <code>n</code> each, but <strong>may</strong>
     * be advanced <em>less</em>.
     *
     * @param memory[2]     (n) The maximum number of words to merge from both lists.
     */
    private void merge(Tape<Integer> a, Tape<Integer> b, Tape<Integer> to) {
        memory[12] = memory[2];
        memory[13] = memory[2];
        while (memory[12] > 0 && null != a.get() &&
               memory[13] > 0 && null != b.get()) {
            if (a.get() < b.get()) {
                to.set(a.get());
                a.advance();
                memory[12]--;
            } else {
                to.set(b.get());
                b.advance();
                memory[13]--;
            }
            to.advance();
        }
        while (memory[12]-- > 0 && null != a.get()) {
            to.set(a.get());
            a.advance();
            to.advance();
        }
        while (memory[13]-- > 0 && null != b.get()) {
            to.set(b.get());
            b.advance();
            to.advance();
        }
    }

    public String toString() {
        StringBuilder sb = new StringBuilder();
        Formatter f = new Formatter(sb);
        f.format("Machine [Tapes: %d, Memory: %d]\n", tapes.length, memory.length);
        for (int i = 0; i < tapes.length; i++) {
            f.format("tape[%d] = %s\n", i, tapes[i].toString());
        }
        for (int i = 0; i < memory.length; i++) {
            if (0 == i % 8) f.format("\n%04x: ", i);
            f.format("%04x ", memory[i]);
        }
        f.flush();
        return sb.toString();
    }
}

Makefile

TARGET ?= target

SP ?= src:$(SOURCEPATH)
TP ?= test:$(SP)
CP ?= $(TARGET):$(CLASSPATH)

JAVA = java
JAVAC = javac

vpath %.java $(SP) $(TP)

objects = Tape Machine SortTest

classes = $(patsubst %,$(TARGET)/%.class,$(subst .,/,$(objects)))

.PHONY: all clean test ;

all: $(classes) ;

clean:
	-rm -r $(realpath $(PWD)/$(TARGET))

test: all
	( cd $(TARGET) && $(JAVA) SortTest )

$(TARGET)/:
	mkdir -p $@

$(TARGET)/%.class: %.java | $(TARGET)/
	$(JAVAC) -d $(TARGET) -classpath $(CP) -sourcepath $(SP) $(JAVA_OPT) $<

SortTest.java

import java.util.List;
import java.util.LinkedList;
import java.util.ArrayList;
import java.util.Arrays;

public class SortTest {
    public static void main(String[] args) {
        List<List<Integer>> data = new LinkedList();

        data.add(new ArrayList<Integer>(Arrays.asList( 0 )));
        // 0..64
        data.add(new ArrayList<Integer>(Arrays.asList(
            5, 51, 25, 3, 41, 36, 49, 40, 29, 59, 39, 46, 45, 22,
            21, 20, 18, 16, 35, 53, 13, 26, 47, 52, 7, 42, 33, 44,
            43, 17, 9, 64, 58, 62, 28, 23, 60, 4, 8, 15, 54, 56,
            38, 31, 30, 37, 14, 55, 24, 10, 1, 63, 11, 19, 6, 50,
            57, 34, 48, 12, 0, 2, 61, 32, 27
        )));
        // 0..256
        data.add(new ArrayList<Integer>(Arrays.asList(
            170, 0, 48, 10, 103, 194, 217, 59, 187, 60, 116, 80,
            94, 151, 221, 76, 25, 135, 176, 20, 167, 100, 125, 228,
            152, 106, 205, 181, 50, 234, 12, 17, 81, 174, 158, 128,
            16, 165, 18, 247, 73, 29, 244, 157, 102, 186, 237, 28,
            49, 252, 171, 63, 21, 172, 154, 224, 169, 123, 53, 64,
            66, 38, 208, 44, 67, 134, 147, 77, 199, 255, 207, 24,
            219, 220, 41, 37, 45, 119, 253, 163, 225, 168, 175, 72,
            235, 162, 30, 254, 160, 84, 206, 229, 146, 51, 215,
            183, 22, 209, 97, 245, 109, 87, 58, 82, 214, 164, 5,
            222, 177, 36, 35, 239, 256, 198, 242, 112, 156, 23,
            218, 159, 34, 230, 126, 113, 203, 31, 250, 2, 179, 11,
            129, 212, 185, 121, 78, 71, 216, 145, 96, 197, 88, 213,
            68, 202, 232, 248, 117, 148, 8, 6, 40, 110, 150, 132,
            93, 14, 69, 142, 98, 143, 120, 193, 118, 39, 223, 57,
            115, 101, 114, 65, 201, 95, 240, 246, 138, 89, 32, 26,
            137, 133, 54, 188, 236, 210, 4, 91, 104, 130, 233, 195,
            75, 3, 251, 191, 52, 33, 124, 226, 196, 122, 139, 107,
            180, 227, 108, 90, 131, 9, 211, 144, 243, 61, 74, 136,
            140, 70, 111, 149, 42, 86, 85, 127, 241, 189, 200, 56,
            141, 166, 192, 27, 92, 178, 231, 204, 105, 13, 7, 153,
            62, 173, 79, 184, 55, 46, 182, 99, 19, 249, 1, 190,
            161, 155, 83, 43, 47, 15, 238
        )));

        for (List<Integer> set : data) {
            Integer[] set_arr = set.toArray(new Integer[0]);
            Machine sorter = new Machine(20,100,set_arr);
            Tape<Integer> check = sorter.sort();
            check.rewind();

            Arrays.sort(set_arr);
            int i = 0;

            while(null != check.get()) {
                if (! check.get().equals(set_arr[i++])) {
                    throw new RuntimeException("Unsorted list! Expected " +
                            set_arr[i-1] + " but got " +
                            check.get() + " at index " + (i-1));
                }
                check.advance();
            }
            if (i != set_arr.length) {
                throw new RuntimeException("Incomplete list! Expected " +
                        set_arr.length + " elements but got " +
                        i + " elements.");
            }
        }
    }
}

Tape.java

import java.util.List;
import java.util.LinkedList;
import java.util.ListIterator;
import java.util.Collection;
import java.util.Collections;
import java.util.Formatter;

public class Tape<T> {
    private List<Maybe<T>> tape;
    private ListIterator<Maybe<T>> it;
    private Maybe<T> current;

    private class Maybe<V> {
        private V v;
        public Maybe() { this.v = null; }
        public Maybe(V v) { this.v = v; }
        public void set(V v) { this.v = v; }
        public V get() { return this.v; }
        public String toString() {
            if (null == get()) return "_";
            return get().toString();
        }
    };

    /**
     * Create a new empty {@link Tape}.
     */
    public Tape() {
        this(Collections.EMPTY_LIST);
    }

    /**
     * Create a new {@link Tape} and populate it with <code>elems</code>.
     */
    public Tape(Collection<? extends T> elems) {
        tape = new LinkedList<Maybe<T>>();
        for (T elem : elems) {
            tape.add(new Maybe<T>(elem));
        }
        it = tape.listIterator(0);
        advance();
    }

    /**
     * Advance the tape head by 1. O(1) operation.
     */
    public void advance() {
        if (!it.hasNext()) {
            it.add(new Maybe<T>());
            it.previous();
        }
        current = it.next();
    }

    /**
     * Get the value at the current tape head. O(1) operation.
     *
     * @return The value at the current tape head.
     */
    public T get() {
        return current.get();
    }

    /**
     * Set the value at the current tape head to <code>o</code>. O(1) operation.
     *
     * @param o The value write to the current tape head.
     */
    public void set(T o) {
        current.set(o);
    }

    /**
     * Rewind the tape to the beginning. O(N) operation.
     */
    public void rewind() {
        while (it.hasPrevious()) {
            it.previous();
        }
        advance();
    }

    public String toString() {
        StringBuilder sb = new StringBuilder("Tape [");
        Formatter f = new Formatter(sb);

        for (Maybe<T> elem : tape) {
            f.format((elem == current ? "^%s," : "%s,"), elem.toString());
        }

        f.format("]");
        f.flush();
        return sb.toString();
    }
}