Suppose we take the n elements to sort and split them into piles
S and T, each with half the elements.
After sorting both piles, it is easy to combine the two sorted piles.
To merge 
and 
, note that the smallest
item must sit at the top of one of the two lists.
Once identified, the smallest element can be
removed, and the second smallest item will again be atop one of the two lists.
Repeating this operation merges the two sorted lists in O(n) time.
This provides the basis for a recursive algorithm.
Mergesort(A[1,n])
Merge( MergeSort(
), MergeSort(
) )
Because the recursion goes 
levels deep and a linear amount of
work is done per level, Mergesort takes 
time in the worst
case.
Mergesort is a classic divide-and-conquer algorithm. Whenever we can break one large problem into two smaller problems, we are ahead of the game because the smaller problems are easier. The trick is taking advantage of the two partial solutions to put together a solution of the full problem. The merge operation takes care of the reassembly in mergesort, but not all problems can be so neatly decomposed.