Lecture 14

Lecture 14, Thu 02/22

Merge Sort

Merge Sort

Merge Sort uses a divide and conquer strategy to perform sorting in a more efficient manner
Idea:
- Break a list into sublists where size == 1 (done recursively)
  - Note that a list with size == 1 is considered sorted
- Merge the sublists together to form a larger list consisting of all elements from both lists in sorted order
- Continue to merge until the list you end up with contains all elements of the original list in sorted order
Example

Merge sort breaks the list into two “equal” parts per recursive call (note that if there’s an odd number of elements it won’t be completely equal)
Just like binary search, by halving the list we are working with each time, we are creating a logarithmic algorithm
On each merge step, at most n comparisons occur (as the merge steps puts the lists together)
Therefore, if n comparisons occur on log n levels, the overall runtime is O(n log n)

List slicing operations using [:] return a new list object, and do not perform an in place modification
During merge sort, one of the tradeoffs is the extra space taken up with every slice operation that is performed (every time a the list is “halved”
- However, the actual list modifcation can be done in place since lists are a mutable type in Python (a new sorted list won’t need to be created from scratch)