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.
Wow… I just plugged that in and it worked perfectly… Except I need to do a reverse sort.
Since it makes my brain hurt, is there any chance you can provide this?
Thanks,
Russell Schutte
@Russell, glad it works out of the box for you. It does make the brain hurt a bit.
Without testing it… try changing the first if statement in Merge() to:
if ( leftArray[ 1 ][ key ] >= rightArray[ 1 ][ key ] ) {
(Note the <= sign has changed to greater than or equal to)
You totally rock!
That did it. I’m sorting about 600 elements in a complex array of structures and this worked fast - and perfectly.
For others viewing, you can also call the function:
products = MergeSort( products, “price” );
Not quite as clear in code, but saves the variable memory.
Thanks again,
Russell Schutte
http://www.russellschutte.com
hey I tried your code as function in cfc. I can’t seem to get it to work. it break up the array properly but after
leftArray = MergeSort(leftArray, key);
rightArray = MergeSort (rightArray, key);
the arrayLen for left and right Array is zero through out as it walks up the recursion, and returns an empty array at the end.
Any idea why this might be?
@Jaysheel - Could you provide more info? Have you tried the function with the simple example code in the blog post? I’ve been using this in production for some time now and it seems stable.
Hey,
Nice function. Its much slicker than a crude Bubble Sort i was using, however your sort is a little slower.
Is it possible that null values will slow this sort down? I’m trying to sort a ton of scores in a golf league and if a person is a no-show, they have no score and need to drop to the bottom.
Hey Brian, Thanks for the feedback. Interesting that you find performance slow, the reason I implemented this is because the bubble sort was so slow and occasionally caused my template to bomb out.
How many rows are in your array?
Hey Ant, thanks for the code and technique. Very handy! Quick question, have you ever adapted this or used another technique to sort arrays of (the same kind of) objects in CFML?
As an example, say I have an array of product objects and I want to sort that array by product price.
Thanks!
Brian
Hi Brian, as I mentioned, I have written a bubble sort routine that I used for a while but found it didn’t perform as well on large arrays.
As for an array of product objects sorted by price - the example above shows how this might work. Is your array setup differently?
Cheers, Ant