- We randomize the array before sorting to avoid worst-case performance.
- We always choose the first element in the partition to be the pivot.
- We used the bottom-up approach.
- We used a third array of size n to help with merging two subarrays of size n/2.
- We used a max-heap.
- In every iteration, we select the minimum from the unsorted and put it in the right place.
- In every iteration, we insert a new number into the sorted numbers.
- BubbleSort works because we will move the smallest discovered to the left one step at a time.
- When the range of input is large, CountingSort may take a huge amount of space.
- It's useful when the input has a small amount of variety within a small range. And the input range can be mapped to array indices easily.
- While CountingSort only uses an auxiliary array to keep track of the counts, PigeonHoleSort creates an auxiliary array to store numbers, or perhaps references to objects (for example, pigeons). [5]
- It's a scatter-gather approach. [1]
- Visualizations
- "The worst-case scenario occurs when all the elements are placed in a single bucket. The overall performance would then be dominated by the algorithm used to sort each bucket." [3]
- "Radix is a Latin word for 'root'. 'Root' can be considered a synonym for base, in the arithmetical sense." [4] Base-10-sort, alphabet-sort.
- Sort digit by digit from the most significant bit to the least significant bit or from the least significant bit to the most significant bit.
- It's also known as monkey sort, stupid sort, random sort, and permutation sort. [2]
- It's a highly inefficient sorting algorithm. [2]
- Time: O(n^2) Space: O(1)
- You find and flip the largest element to the front. And then you flip the largest element to the end. Repeat the process until the arry is sorted.
- The algorithm was published in 1959 and was named after its inventor Donald Shell. [7]
- It's also known as the "diminishing increment sort." [8]
- Researchers are still deciding the optimal diminishing increments for large N. [8]
- The last sort of gap size 1 is an insertion sort. [10]
- https://www.programiz.com/dsa/bucket-sort
- https://en.wikipedia.org/wiki/Bogosort
- https://en.wikipedia.org/wiki/Bucket_sort
- https://en.wikipedia.org/wiki/Radix
- https://en.wikipedia.org/wiki/Pigeonhole_sort
- http://penguin.ewu.edu/cscd300/Topic/AdvSorting/p30-shell.pdf
- https://dl.acm.org/doi/10.1145/368370.368387
- Knuth, Donald E. (1997). "Shell's method". The Art of Computer Programming. Volume 3: Sorting and Searching (2nd ed.). Reading, Massachusetts: Addison-Wesley. pp. 83–95. ISBN 978-0-201-89685-5.
- Sedgewick, Robert. 1996. “Analysis of Shellsort and Related Algorithms.” Fourth Annual European Symposium on Algorithms, September. https://www.cs.princeton.edu/~rs/shell/.
- Edwards, Rob. 2016. Sorts 5 Shell Sort. https://www.youtube.com/watch?v=ddeLSDsYVp8.