Sorting Algorithms

Sorting Algorithm? Stable? In-Place?

Sorting Algorithms Comparison

Name	Best	Average	Worst	Memory	Stable	Method	Other notes
Quicksort	`nlog(n)`	`nlog(n)`	`n^2`	`log(n)`	No	Partitioning	Quicksort is usually done in-place with `O(log(n))` stack space.
Merge sort	`nlog(n)`	`nlog(n)`	`nlog(n)`	`n`	Yes	Merging	Highly parallelizable (up to `O(log(n))` using the Three Hungarians’ Algorithm).
In-place merge sort	—	—	`n(log(n)^2)`	`1`	Yes	Merging	Can be implemented as a stable sort based on stable in-place merging.
Heapsort	`nlog(n)`	`nlog(n)`	`nlog(n)`	`1`	No	Selection
Insertion sort	`n`	`n^2`	`n^2`	`1`	Yes	Insertion	`O(n + d)`, in the worst case over sequences that have d inversions.
Timsort	`n`	`nlog(n)`	`nlog(n)`	`n`	Yes	Insertion & Merging	Makes n comparisons when the data is already sorted or reverse sorted.
Selection sort	`n^2`	`n^2`	`n^2`	`1`	No	Selection	Stable with `O(n)` extra space or when using linked lists.
Bubble sort	`n`	`n^2`	`n^2`	`1`	Yes	Exchanging	Tiny code size.
Gnome sort	`n`	`n^2`	`n^2`	`1`	Yes	Exchanging	Tiny code size.

Merge Overlapping Intervals
- For example,
  let the given set of intervals be {{1,3}, {2,4}, {5,7}, {6,8}}. The intervals {1,3} and {2,4} overlap with each other, so they should be merged and become {1,4}. Similarly, {5,7} and {6,8} should be merged and become {5,8}
- Solution:
  - Sort the intervals and then merge them in a linear fashion