Merge Sort in Bash

Thanks to Adam Vite for this.

So, 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.
#

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 \$@ ; 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.
#

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;
}

2 thoughts on “Merge Sort in Bash”

1. K says:

Uh…. i’d love to use this, except i’ve never cared to sort things. If i did, i might use the awesome “sort” command….

Also, 1330 numbers in 35 seconds is horrible. Why don’t you implement bubblesort. Might go the same speed …

1. termina says:

You really shouldn’t use this; it was a quick thing he did for fun after taking a data structures and algorithms class in college.

It was posted here as something interesting, not something I would suggest people use.