After a recent spell of doing lots of prototyping, I’m finally getting back to some proper coding. I have an array of structures that I’d been sorting on a particular key (price) using a quick bubble sort algorithm. However, with real data on the site it was randomly returning errors and proving fairly unstable.
I knew there were better algorithms out there, so I thought I’d try a Merge Sort, and wrote a version in cfscript… posted here for your pleasure 
<cfscript>
/**
* Sorts an array of structures using the Merge Sort algorithm.
*
* @param arr The array to sort. (Required)
* @param key Structure Key to sort by (Required)
* @return Returns an array.
* @author Anthony Cooper (ant@outsrc.co.uk)
* @version 1, 8 Feb 2008
*/
function MergeSort( arr, key ) {
var leftArray = ArrayNew( 1 );
var rightArray = ArrayNew( 1 );
var result = ArrayNew( 1 );
var middle = 0;
var i = 0;
if ( ArrayLen( arr ) LTE 1 ) {
return arr;
}
else {
middle = Ceiling( ArrayLen( arr ) / 2 );
for ( i = 1; i LTE middle; i++ ) {
ArrayAppend( leftArray, arr[ i ] );
}
for ( i = ( middle + 1 ); i LTE ArrayLen( arr ); i++ ) {
ArrayAppend( rightArray, arr[ i ] );
}
leftArray = MergeSort( leftArray, key );
rightArray = MergeSort( rightArray, key );
result = Merge( leftArray, rightArray, key );
return result;
}
}
function Merge( leftArray, rightArray, key ) {
var result = ArrayNew( 1 );
while ( ArrayLen( leftArray ) > 0 AND ArrayLen( rightArray ) > 0 ) {
if ( leftArray[ 1 ][ key ] <= rightArray[ 1 ][ key ] ) {
ArrayAppend( result, leftArray[ 1 ] );
ArrayDeleteAt( leftArray, 1 );
}
else {
ArrayAppend( result, rightArray[ 1 ] );
ArrayDeleteAt( rightArray, 1 );
}
}
if ( ArrayLen( leftArray ) > 0 ) {
result = ArrayJoin( result, leftArray );
}
if ( ArrayLen( rightArray ) > 0 ) {
result = ArrayJoin( result, rightArray );
}
return result;
}
function ArrayJoin( firstArray, secondArray ) {
var i = 0;
for ( i = 1; i <= ArrayLen( secondArray ); i++ ) {
ArrayAppend( firstArray, secondArray[ i ] );
}
return firstArray;
}
</cfscript>
And here’s how you’d use it…
<cfscript>
products = ArrayNew( 1 );
products[1] = { name = "Jacket", price = "2999" };
products[2] = { name = "Shoes", price = "2199" };
products[3] = { name = "Slacks", price = "1999" };
sortedProducts = MergeSort( products, "price" );
</cfscript>
Disclaimer: I’m not claiming this is perfect, and I know it could be improved upon and sort direction etc added. But it was a quick solution to my problem. I’d be interested in others feedback.
