This way for example:
/**
* Use insertion-sort for small arrays
* @access private
*/
private static const INS_SORT:int = 4;
/**
* We are using merge-sort instead of Array#sort(..), because we
* want to have a stable sorting algorithm.
*
* @access private
*/
function mergesort ( arr:Array, lo:int, hi:int ) :Array {
var len_1:int = hi - lo;//length - 1
if (len_1 < LzReplicationManager.INS_SORT) {
//length is in [0..4], use insertion-sort
var r:Array = arr.slice(lo, hi + 1);
var tmp:*;
for (var i:int = 1; i <= len_1; ++i) {
for (var j:int = i; j > 0; --j) {
if (this.orderf(r[j], r[j - 1]) == 1) {
tmp = r[j];
r[j] = r[j - 1];
r[j - 1] = tmp;
} else {
break;
}
}
}
return r;
} else {
var mid:int = lo + Math.floor( len_1 / 2 );
var a:Array = this.mergesort( arr, lo, mid );
var b:Array = this.mergesort( arr, mid + 1, hi );
if (this.orderf(a[mid], b[mid + 1]) == 1) {
//both lists are sorted, no need to merge
return a.concat(b);
}
//now merge
var r:Array = [];
var ia:int = 0;
var ib:int = 0;
var al:int = a.length;
var bl:int = b.length;
while ( ia < al && ib < bl ){
if ( this.orderf( b[ ib ], a[ ia ] ) == 1 ){
r.push( b[ ib++ ] );
} else {
r.push( a[ ia++ ] );
}
}
while ( ia < al ) r.push( a[ ia++ ] );
while ( ib < bl ) r.push( b[ ib++ ] );
return r;
}
}
On 6/28/2008 12:41 AM, André Bargull wrote:
I meant insertionsort.
On 6/28/2008 12:38 AM, André Bargull wrote:
I see. But at least we could consider to improve the merge-sort, e.g.
for small instances you can use selectionsort/insertionsort (I always
confuse them with each other), to avoid recursion and creation of
1-length array objects etc.
On 6/28/2008 12:20 AM, P T Withington wrote:
Be careful. Array#sort is not stable. I think we have our own sort
because we want a stable sort. Also, I think Adam got the sign of
the sort result backwards from the built-in, so you would have to
compensate for that even if you gave up stability.
Perhaps add a comment to the code for future archaeologists.
On Jun 27, 2008, at 16:23, André Bargull <[EMAIL PROTECTED]> wrote:
How about to file as an improvement-request at Jira, so it doesn't
get lost?
- André
On 5/8/2008 4:32 PM, André Bargull wrote:
Please just remove it, that's a standard merge-sort without any
adjustments, so Array#sort(..) should be much faster.
I just found this method. Do we still think that a Javascript
sort method is needed? How could it possibly be as fast as the
built-in Array#sort method?
