Ant Cooper

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.