Merge Sort
Algorithm
- Split the list into the smallest components.
- Compare adjacent elements and perform swaps placing elements in order.
- Continue to merge the partitions until the list is sorted.
Performance
- Worst case:
- Best case:
- Average case:
- Space complexity:
for a table, 
for a list.