Mergesort vs Quicksort

Mergesort
- O(nlogn)
- Preferred over Quicksort for Linked Lists
	- Linked nodes may not be adjacent in memory (Quicksort may not take advantage of cache)
	- Can insert items in middle of list in O(1) time/space, so merge sort can be implemented without extra space
	- Quicksort requires a lot of random accessing in arrays (ie A[i]), which cannot be done in linked lists
- Does fewer comparisons, so may be better when complicated comparison routines are used
- Divide-then-conquer algorithm. The partitioning happens in a trivial way, by splitting the input array in half. Most of the work happens during the recursive calls and the merge phase

Quicksort
- O(n^2). Theta(nlogn).
- Preferred over Mergesort for arrays
	- Doesn't have to create new arrays for merging (Mergesort has to allocate/deallocate arrays)
- Often faster for smaller arrays, and on arrays of a few distinct values repeated many times
- Conquer-then-divide algorithm, which does most of the work during the partitioning and the recursive calls. The subsequent reassembly of the sorted partitions involves trivial effort
- Considered faster than merge since it is
	- in-place (arguable since requires O(n) auxiliary space for call stack)
	- cache-friendly (working on same array, so more cache hits than merge - main reason why this is faster)
	- tail recursive (can rewrite last recursive call to iterative implementation -  Python does not automatically do this for
	  	optimization, but other languages do).

Sources:
- https://rosettacode.org/wiki/Sorting_algorithms/Quicksort#:~:text=%22On,phase.
- https://www.geeksforgeeks.org/quick-sort/#:~:text=why%20quick%20sort%20is%20preferred%20over%20mergesort%20for%20sorting%20arrays%20%3F