Merge sort

belongs to “divide and conquer”

1. if only one element remaining in list, it is sorted — return
2. divide list recursively into two halves until no longer divided
3. merge smaller list into new list in sorted order

Time complexity:

• Best case: O(nlogn)
• Worst case: O(nlogn)