/* Merge Sort, increasing order */

#include "harp1.h"

const dw = 9;
const aw = 8;
const ae = (1 << aw);

main (chan (in)  STDIN          : dw,
      chan (out) STDOUT         : dw,
      eram data[ae] = harp1lram : dw,
      eram temp[ae] = harp1hram : dw)
{
    int a, b;
    int start, addr;
    int rel_a, rel_b, abs_c;
    int length : aw;

    int a_lt_b() = a < b;

    int abs_a() = rel_a + start;
    int abs_b() = rel_b + start + length;

    int rel_a_eq_length() = (rel_a == length);
    int rel_b_eq_length() = (rel_b == length);


    void inc_addr() {
	addr = addr + 1;
    }

    void merge() {
	
	length = 1;

	/* For sorted pairs of lists of lengths 1, 2, 4, 8 ... */
	do {

	    /* For each pair of lists of length "length" */
	    do {

		rel_a, rel_b, abs_c = 0, 0, start;

		a = data[abs_a()];
		b = data[abs_b()];

		do {
		    if ((a_lt_b() & ~rel_a_eq_length()) | rel_b_eq_length())
			par {
			    temp[abs_c], a = a, data[abs_a() + 1];
			    rel_a, abs_c = rel_a + 1, abs_c + 1;
			}
		    else
			par {
			    temp[abs_c], b = b, data[abs_b() + 1];
			    rel_b, abs_c = rel_b + 1, abs_c + 1;
			}
		} while (~(rel_a_eq_length() & rel_b_eq_length()));

		/* Skip a pair */
		start = start + (length << 1);

	    } while (start != 0);

	    /* Copy the entire data from the temporary area */
	    do par {
		data[addr] = temp[addr];
		inc_addr();
	    } while (addr != 0);
	    
	    length = length << 1;
	    
	} while (length != 0);

    }
    
    void input_data() {
	do par {
	    STDIN ? data[addr];
	    inc_addr();
	} while (addr != 0);
    }
    

    void output_data() {
	do par {
	    STDOUT ! data[addr];
	    inc_addr ();
	} while (addr != 0);
    }
		

    /* Main Program */

    input_data();
    merge();
    output_data();
}