mergesort.js

mergesort.js

function mergeSort(array){
    //
    if( array.length <= 1 ) return;

    // division phase
    var leftSize	= Math.floor(array.length / 2),
		rightSize	= array.length - leftSize,
	 	left		= array.slice(0, leftSize),
	 	right		= array.slice(leftSize);

    // recursion phase
    mergeSort( left );
    mergeSort( right );

    // merge phase
    var L = 0,
 		R = 0;
 	
    while(
        ( L < leftSize  ) ||
        ( R < rightSize )
	){
        if( rightSize <= R ){
            array[L + R] = left[L];
            ++L;
        } else if( leftSize <= L ){
            array[L + R] = right[R];
            ++R;
        } else if( left[L].value > right[R].value ){
            array[L + R] = right[R];
            ++R;
        } else {
            array[L + R] = left[L];
            ++L;
        }
    }
    return array;
}