Pseudo Code

mergeSort(array):
   if length(array) <= 1:
      return array
   mid = length(array) / 2
   left = mergeSort(array[0..mid])
   right = mergeSort(array[mid..end])
   return merge(left, right)

merge(left, right):
   result = []
   while left and right both still have elements:
      if left[0] <= right[0]:
         move the front of left into result
      else:
         move the front of right into result
   append whatever remains of left
   append whatever remains of right
   return result