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. |

## Sorting Problems

- 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

- For example,