## Sorting Algorithms

### How to sort elements in a list? What are the common sorting algorithms? Which sorting algorithm to use? How do they fare against each other?

Sorting Algorithm? Stable? In-Place?

## Sorting Algorithms Comparison#

NameBestAverageWorstMemoryStableMethodOther notes
Quicksort`nlog(n)``nlog(n)``n^2``log(n)`NoPartitioningQuicksort is usually done in-place with `O(log(n))` stack space.
Merge sort`nlog(n)``nlog(n)``nlog(n)``n`YesMergingHighly parallelizable (up to `O(log(n))` using the Three Hungarians’ Algorithm).
In-place merge sort`n(log(n)^2)``1`YesMergingCan be implemented as a stable sort based on stable in-place merging.
Heapsort`nlog(n)``nlog(n)``nlog(n)``1`NoSelection
Insertion sort`n``n^2``n^2``1`YesInsertion`O(n + d)`, in the worst case over sequences that have d inversions.
Timsort`n``nlog(n)``nlog(n)``n`YesInsertion & MergingMakes n comparisons when the data is already sorted or reverse sorted.
Selection sort`n^2``n^2``n^2``1`NoSelectionStable with `O(n)` extra space or when using linked lists.
Bubble sort`n``n^2``n^2``1`YesExchangingTiny code size.
Gnome sort`n``n^2``n^2``1`YesExchangingTiny 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