#!/bin/bash

# This is a toy, do not use for large files!
# It takes almost a second to sort my 40 line /etc/passwd file!

# protect the user:
ulimit -u 500

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() {
	
	# handle trivial sorts with 0 or 1 items
	get line1 || return
	get line2 || { echo "$line1"; return; }
	
	# make pipes for sub-processes
	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"
	
	# splitter process
	(
		echo "$line1"
		echo "$line2" >&3
		split_odds_evens
	) <&0 >"$p_1i" 3>"$p_2i" &
	
	# recursive sorts
	mergesort <"$p_1i" >"$p_1o" &
	mergesort <"$p_2i" >"$p_2o" &
	
	# merge process
	merge <"$p_1o" 3<"$p_2o" >&1 &
	
	# wait for sub-processes to finish
	wait
	
	# remove pipes
	rm "$p_1i" "$p_1o" "$p_2i" "$p_2o"
}

mergesort