Merge Sort
[Divide and Conquer paradigm](https://texonom.com/divide-and-conquer-paradigm-9b10e85e70214b9b8f0bd293f5c297bd) [Von Neumann](https://texonom.com/von-neumann-ef79cb1b1e9045d28caced75663e14f7) 


$$T(n) = 2T(n/2) + \Theta(n)$$
- 2 means 2 sub problems
- n/2 means subproblem size
- $\Theta(n)$ means work dividing and combining
> ![](https://www.notion.so/image/https%3A%2F%2Fprod-files-secure.s3.us-west-2.amazonaws.com%2F0bf522c6-2468-4c71-99e3-68f5a25d4225%2F5a20f9a4-1e1b-49d7-b159-36184316ad5e%2FUntitled.png?table=block&id=54fc5c72-847c-412d-a626-91856efc63c0&cache=v2)


### Practive
- merge sort beats insertion sort for $n>30$



> [Merge sort](https://en.wikipedia.org/wiki/Merge_sort)





