Sorting
Sorting is the process of putting a collection in a particular ordered manner. The ordering is straightforward for certain data types like numbers and strings (lexicographically) but it can always be customized. There are two sort orders provided, ascending or descending.
There are many different sorting algorithms, each with own pros and cons; maybe bogosort doesn't have any pros. The fastest algorithms which involves comparing elements to one another are O(n log n). There are a few faster algorithms that can be faster but there are restrictions involved.
| Pros | Cons |
|---|---|
| Opens up more options for solving problems; binary search becomes a possibility. | So many different sorting options. |
| Easy to find min or max elements in a sorted collection | Typically solutions aren't faster than O(n log n) when using a comparison sort |
| Name | Worst | Average | Best | Memory | Tags | Notes |
|---|---|---|---|---|---|---|
| Counting sort | O(n+k) | O(n+k) | Non-comparison sort Stable sort | |||
| Heapsort | O(nlog n) | O(nlog n) | O(nlog n) | O(n) | Comparison sort In-place | |
| Insertion sort | O(n^2) | O(n^2) | O(n) | O(n) | Comparison sort In-place Online algorithm Stable sort | |
| Merge sort | O(nlog n) | O(nlog n) | O(nlog n) | O(n) | Comparison sort Stable sort | |
| Quicksort | O(n^2) | O(nlog n) | O(nlog n) | O(log n) | Comparison sort In-place |
LeetCode Problems
