Quicksort in 3 lines of shell

    qsort(){
        local L="";
        local G="";
        [ $# -eq 1 ] && echo $1 && return;
        P=$1; 
        shift; 
        for i in $@; do 
            [ $i -lt $P ] && L="$L $i" || G="$G $i"; 
        done
        [ -z "$L" ] || L=`qsort $L`; 
        [ -z "$G" ] || G=`qsort $G`; 
        echo "$L $P $G"
    }
    qsort $@

POSIX has standardized $(qsort $L) syntax since 1990. It's okay to use it now.

First it appears it has the classic bug of passing items equal to the partition to sub-sorts (G in this case). This guarantees N recurses (and at least c N^2 operations) when trying to sort an array that is all duplicates of a single value. Also the list concatenations ( L="$L $i" and G="$G $i") which often make mere list assembly take c N^2 time (pretty much forced by the string representations). So this could be a c N^3 worst-case sorting algorithm (possibly worse than bubble sort).

One of my articles on the pain of quicksort: http://www.win-vector.com/blog/2008/04/sorting-in-anger/

void qs( int* a , int z )

{

if(z > 1){ ; int p = a[z/2], s = 0, e = z-1, t; while(s <= e) {

for(;a[s] < p; s++); for(;a[e] > p; e--); if(s <= e) { t = a[s];

a[s++] = a[e]; a[e--] = t; } } qs( a , e+1 ); qs( a+s , z-s ); }

}

I what must be a lapse of sanity, I wrote mergesort. It is quite a bit more than 3 - err, 14 - lines, but it does include an option to see view the array nesting.

It uses slightly better array management... and then throws out any gains by rebuilding a new array every time an element is shift off the front.

// for when you really don't want to use sort(1)

:%s/\n/ /g