Merge Sort

sort(S): sort sequence S

1. if (isEmpty(S) || S is singleton) return S;

2. split S evenly into two parts S1 and S2

3. sortedS1 = sort(S1);

4. sortedS2 = sort(S2);

5. return merge(S1,S2);