Merge Sort

if the size of the List is at least 2  
  split the List into the left half and the right half  
  recursively sort left  
  recursively sort right  
  merge left and right into one List  
end if

mergeSort ( list ) {
if ( list.size > 1 ) {
split( list, left, right );
mergeSort( left );
mergeSort( right );
merge( left, right, list );
}
}

split ( list, left, right ) {
for each item in the left half of list (less than or equal to middle index)
add the item to left
for each item in the right half of list (greater than middle index)
add the item to right
}

merge( left, right, list ) {
while both left and right have more items
if the left item is less than the right item
add the left item to list
else
add the right item to list
while left has more items
add the left item to list
while right has more items
add the right item to list
}