# Merge Sort

This is probably one of the sorting algorithms that I have a lot of difficulty understanding, alongside Quick Sort.

This algorithm takes more space, so it’s a tradeoff. It’s a Divide and Conquer algorithm.
**High Level Idea:**

- Divide array in half
- Sort each half recursively following the same algorithm
- Merge the results

### Time Complexity

- Worst Case: $O(ngn)$
- Average Case: $O(ngn)$
- Best Case: $O(n)$

### Space Complexity

### Merge Sort Pseudocode

We can logically divide without physically dividing an array.

From Mari Programming class

Bottom up merge sort