A SleepSort using Multiprocessing in BASH

In [here], the implementation of a sleep-sort algorithm is presented via the Python code. This article will shortly presents the implementation in Linux BASH Shell Script, which demonstrates the very basics of multiprocessing in Linux e.g. Ubuntu 11 environment, using the BASH.

The idea of sleepsort is simple. According to the value of the elements, sleep some interval and print the value. The multiprocessing in BASH is even simpler, i.e. you just need to place the & sign after the command and that command will be run in background, which easily enables multi-tasking.

The BASH Script is given below.

#!/bin/sh
# sleepsort
# helloacm.com

sleepNprint()
{
	if [ -z "$1" ]
	then
		exit
	fi
	# sleep and print
	sleep $1
	echo -n "$1 "
}

sort()
{
	for i in $1
	do
		# use & to launch in background
		sleepNprint $i&
	done
}

inputArr="9 8 2 3 4 5 1"
sort "$inputArr"

The structure is straightforward. First define the array (actuall not an array but simply a string). Define a sort function which parse the input string. In the function, launch the sleep thread (i.e. process) in the background which sleeps some interval and prints out the value.

In the future, this script will be improved by adding synchronization support. There will be a waiting for all processes to finish before the main script exits. Also, instead of simply printing the value, an array will be held to keep all the sorted elements. In this case, there will be the need of enable critical section (e.g. locks) to prevent simutaneous access to the same variables.

One akward moment would be passing a relative large number, for example, 99999, and the sleep sort will need to sleep for quite a long time. However, the space complexity for this algorithm is really . The following code will be shorter and simpler.

#!/bin/bash
f() 
{
    sleep "$1"
    echo "$1"
}
while [ -n "$1" ]
do
    f "$1" &
    shift # shift one parameter to the left
done
wait

The shift will effectively loop each parameter i.e. [ -n “$1” ] will test if $1 is empty.

–EOF (The Ultimate Computing & Technology Blog) —