Divide the list into two until all elements are by them selves
Merge pairs of lists, putting elements back in the correct order
Pseudocode
a = list
n = size of list
mergesort(array a)
if (n == 1)
return a
arrayOne = a[0 : n/2]
arrayTwo = a[(n/2)+1 : n]
arrayOne = mergesort(arrayOne)
arrayTwo = mergesort(arrayTwo)
return merge(arrayOne, arrayTwo)
merge(array a, array b)
array c
while(a and b has elements)
if(a[0] > b[0])
c.push_back(b[0])
b.pop() // remove b[0]
if(a[0] < b[0])
c.push_back(a[0])
a.pop() // remove a[0]
// there should be no elements left
// in a or b
while(a has elements)
c.push_back(a[0])
a.pop()
while(b has elements)
c.push_back(b[0])
b.pop()
return c