Merge Sort in Bash
Posted in Code, Informational on October 7th, 2013 by hobogodSo, during spring break, I was extremely bored and implimented merge sort into a language that doesn’t really need it: Bash. I got inspiration to do this from seeing merge sort implimented in Prolog. As of right now, it merely sorts integers, but can sort anything, given that a compareTo method of what you want sorted is written into the merge method (bash isn’t object oriented, so it’s not really so adaptable to adaptability.) I doubt I’m the first person to do this, but it’s a nice thought experiment to see how limited languages can still allow the performance of advanced operations. I don’t guarantee that this algorithm performs in n*log(n) time as I’m not sure of the individual costs of bash operations or the cost of reading and executing this, but I tested it with 1330 numbers and it sorted them in about 35 seconds on my 1.6 Ghz laptop.
#!/bin/bash
mrgsrt() {
# This function impliments the merge sort algorithm into bash.
#
# @Author: Adam Vite
if [ $# = 1 ]; then
echo $1;
# There is only one arguement, list is sorted
elif [ $# -gt 1 ]; then
i=0;
unset left;
unset right;
for x in [email protected] ; do
if [ $i -lt $(($# / 2)) ]; then
left=$( echo $left $x );
i=$(($i + 1));
else
right=$( echo $right $x );
fi;
done;
# The arguments have been split in half
left=$( mrgsrt $left );
right=$( mrgsrt $right );
# each half has been sorted recursively
mrg $left $right;
# The two halves have been merged together with a helper method
else
echo "Usage: mrgsrt <series of numbers seperated by spaces>";
fi;
}
mrg() {
# This method sorts two sorted lists of numbers by adding the lowest of
# firstmost unsorted number into a new list until all numbers have been
# added and then returns that list.
#
# @Author: Adam Vite
l=1; # Begining index of left half
r=$(($# / 2 + 1)); # Begining index of right half
unset list;
while [ $l -ne $(($# / 2 + 1)) ] || [ $r -ne $(($# + 1)) ]; do
if [ $l = $(($# / 2 + 1)) ]; then
list=$( echo $list ${!r} );
r=$(($r+1));
# Left half has been sorted
elif [ $r = $(($# + 1)) ]; then
list=$( echo $list ${!l} );
l=$(($l+1));
# Right half has been sorted
elif [ ${!l} -lt ${!r} ]; then
list=$( echo $list ${!l} );
l=$(($l+1));
# Firstmost unsorted left is less than firstmost unsorted right
else
list=$( echo $list ${!r} );
r=$(($r+1));
# Firstmost unsorted right is less than firstmost unsorted left
fi;
done;
echo $list;
}