#!/bin/bash

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

mergesort() {
	get line1 || return
	get line2 || { echo "$line1"; return; }
	tmp_1i=`tempfile` tmp_1o=`tempfile` tmp_2i=`tempfile` tmp_2o=`tempfile`
	rm "$tmp_1i" "$tmp_1o" "$tmp_2i" "$tmp_2o"
	mkfifo "$tmp_1i" "$tmp_1o" "$tmp_2i" "$tmp_2o"
	(
		echo "$line1"
		echo "$line2" >&3
		while get line1; do
			echo "$line1"
			get line2 || break
			echo "$line2" >&3
		done
	) <&0 >"$tmp_1i" 3>"$tmp_2i" &
	mergesort <"$tmp_1i" >"$tmp_1o" &
	mergesort <"$tmp_2i" >"$tmp_2o" &
	(
		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
	) <"$tmp_1o" 3<"$tmp_2o" &
	wait
	rm "$tmp_1i" "$tmp_1o" "$tmp_2i" "$tmp_2o"
}

mergesort