#!/bin/bash

ulimit -u 100

get() {
	IFS= read -r "$1"
}

split_odds_evens() {
	while get line1; do
		echo "$line1"
		get line2 || break
		echo "$line2" >&3
	done
}

merge() {
	get line1 ; fail1=$?
	get line2 <&3 ; fail2=$?
	
	while [ "$fail1$fail2" != "11" ]; do
		if [ "$fail1" = 1 -o \( "$fail2" = 0 -a "$line1" \> "$line2" \) ]; then
			echo "$line2"
			get line2 <&3 ; fail2=$?
		else
			echo "$line1"
			get line1 ; fail1=$?
		fi
	done
}

mergesort() {
	get line1 || return
	get line2 || { echo "$line1"; return; }

	p_1i=`tempfile` p_1o=`tempfile` p_2i=`tempfile` p_2o=`tempfile`
	rm "$p_1i" "$p_1o" "$p_2i" "$p_2o"
	mkfifo "$p_1i" "$p_1o" "$p_2i" "$p_2o"

	(
		echo "$line1"
		echo "$line2" >&3
		split_odds_evens
	) <&0 >"$p_1i" 3>"$p_2i" &

	mergesort <"$p_1i" >"$p_1o" &
	mergesort <"$p_2i" >"$p_2o" &

	merge <"$p_1o" 3<"$p_2o" >&1 &

	wait

	rm "$p_1i" "$p_1o" "$p_2i" "$p_2o"
}

mergesort