再帰を使ったソートアルゴリズム

javascriptでのソートアルゴリズムの実装を

友人がやっていてちょっと面白そうなので自分もやってみた。

// マージソート
(function marge_sort(ary) {
    function marge(x , y) {
      if(!x.length) return y;
      if(!y.length) return x;
      return (x[0] < y[0]) ?
        [x.shift()].concat(marge(x, y)):
        [y.shift()].concat(marge(x, y));
    }

    // ソート処理メイン
    return (function(ary) {
        if (ary.length < 2) return ary;
        var sep = Math.round(ary.length/2);
        var left = arguments.callee(ary.slice(0, sep));
        var right = arguments.callee(ary.slice(sep));
        return marge(left, right);
    })(ary);
}([4,2,8,10,9,7]));
//->[2, 4, 7, 8, 9, 10]


// クイックソート
(function quick_sort(ary) {
	function islow(piv) {
	    return function(e){ return e < piv }
	}
	
	// ここも再帰でも良かったけどあまりにも無駄が多すぎたのでおとなしくループに。
	function partition(ary, fn) {
	    var left = [], right = [];
	    for(var i = 0; i < ary.length; i++) {
	        if (fn(ary[i])) left.push(ary[i]);
	        else right.push(ary[i]);
	    }
	    return {left: left, right: right};
	}
	
	// ソート処理メイン
	return (function qsort(ary) {
	    if (ary.length　< 2) return ary;
	    var pivot = ary.shift();
	    var result = partition(ary, islow(pivot));
	    return qsort(result.left).concat(pivot,qsort(result.right));
	})(ary);
})([5, 3, 2, 9, 1, 6, 11, 3]);
//->[1, 2, 3, 3, 5, 6, 9, 11]


// バブルソート
(function bubble_sort(ary, k) {
	if ((k||0) >= ary.length - 1) return ary;
	
	function swap(ary, i) {
		var tmp = ary[i]; ary[i] = ary[i+1]; ary[i+1] = tmp;
	}
	
	(function sort(ary, i) {
		if (i >= ary.length - 1) return ary;
		if (ary[i] > ary[i + 1]) swap(ary, i);
		return sort(ary, i+1);
	})(ary, 0);
	return bubble_sort(ary, (k||0) + 1);
})([1, 3,1,4, 15, 6, 5, 5, 8, 7]);
//->[1, 1, 3, 4, 5, 5, 6, 7, 8, 15]

クイックソートのところでループを使っているが、
再帰で書くとあまりに無駄が多すぎたのでループにした。
再帰で書くとしたら配列をコピーしてやって、
底から要素を一個ずつ結合していくって感じの処理になるかな。

ヒープソートはやった事がないのでまず理解しないとわかりません。。。