Bubble Sort Explanation
Sorting algorithms can be classified in several ways: by comparison vs. non-comparison, internal vs.
external, stable vs. unstable, in-place vs. out-of-place, and sequential vs. parallel. Below is a
comprehensive list.
1. Comparison-Based Sorting Algorithms
These algorithms sort by comparing elements.
Algorithm Best Average Worst Stable In-place
2 2
Bubble Sort O(n)* O(n ) O(n ) Yes Yes
Selection Sort O(n2 ) O(n2 ) O(n2 ) No Yes
2 2
Insertion Sort O(n) O(n ) O(n ) Yes Yes
Binary Insertion Sort O(n) O(n2 ) O(n2 ) Yes Yes
Shell Sort Depends on gap ~O(n1.3 ) O(n2 ) No Yes
Merge Sort O(n log n) O(n log n) O(n log n) Yes No
Quick Sort O(n log n) O(n log n) O(n2 ) No Yes
Heap Sort O(n log n) O(n log n) O(n log n) No Yes
Tree Sort O(n log n) O(n log n) O(n2 ) Depends No
Tournament Sort O(n log n) O(n log n) O(n log n) No No
Cycle Sort O(n2 ) O(n2 ) O(n2 ) No Yes
Comb Sort O(n log n) O(n2 ) O(n2 ) No Yes
Cocktail Shaker Sort O(n) O(n2 ) O(n2 ) Yes Yes
Odd-Even Sort O(n) O(n2 ) O(n2 ) Yes Yes
Gnome Sort O(n) O(n2 ) O(n2 ) Yes Yes
Pancake Sort O(n2 ) O(n2 ) O(n2 ) No Yes
Strand Sort O(n) O(n2 ) O(n2 ) Yes No
TimSort O(n) O(n log n) O(n log n) Yes No
IntroSort O(n log n) O(n log n) O(n log n) No Yes
Block Sort O(n log n) O(n log n) O(n log n) Yes No
Library Sort O(n) O(n log n) O(n2 ) Yes No
SmoothSort O(n) O(n log n) O(n log n) No Yes
*Bubble Sort achieves O(n) in the best case only with the common early-exit optimization.
2. Non-Comparison Sorting Algorithms
These algorithms do not rely solely on pairwise comparisons.
Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 1/4
Algorithm Best Average Worst Stable In-place
Counting Sort O(n + k) O(n + k) O(n + k) Yes No
Radix Sort O(d(n + k)) O(d(n + k)) O(d(n + k)) Yes No
Bucket Sort O(n + k) O(n + k) O(n2 ) Depends No
Pigeonhole Sort O(n + k) O(n + k) O(n + k) Yes No
Flash Sort O(n) O(n) O(n2 ) No Yes
American Flag Sort O(n) O(n) O(n) No Yes
BurstSort O(n) O(n) O(n) Yes No
Bead Sort (Gravity Sort) O(n) O(n) O(S) Yes No
Here:
k = range of keys.
d = number of digits.
S = sum of the values (for Bead Sort).
3. External Sorting Algorithms
Used when the data is too large to fit into main memory.
Algorithm Main Idea
External Merge Sort Merge sorted chunks stored on disk
Polyphase Merge Sort Efficient tape/disk merging
Balanced Multiway Merge Sort Multiway merging
Cascade Merge Sort Multi-level merge process
Distribution Sort Distribute records into files before merging
4. Parallel Sorting Algorithms
Designed for multicore processors, GPUs, or distributed systems.
Algorithm Application
Bitonic Sort Parallel hardware, GPUs
Odd-Even Merge Sort Parallel processors
Sample Sort Distributed computing
Parallel Merge Sort Multithreading
Parallel Quick Sort Multicore CPUs
Parallel Radix Sort GPUs
Enumeration Sort SIMD architectures
Shear Sort Mesh-connected processors
Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 2/4
5. Hybrid Sorting Algorithms
These combine multiple sorting techniques.
Algorithm Combination
TimSort Merge Sort + Insertion Sort
IntroSort Quick Sort + Heap Sort + Insertion Sort
SpreadSort Radix Sort + Comparison Sort
GrailSort Merge Sort + Block Sort
WikiSort Stable in-place Merge Sort variant
PDQSort Pattern-defeating Quick Sort
Adaptive Merge Sort Merge + Insertion techniques
6. Specialized Sorting Algorithms
Designed for particular types of data or constraints.
Algorithm Purpose
Topological Sort Directed acyclic graphs (DAGs)
Sleep Sort Novelty/joke algorithm
Stooge Sort Educational only
Bogosort Random permutation until sorted
Bozo Sort Random swaps
Slow Sort Recursive educational algorithm
Permutation Sort Generate all permutations
Spaghetti Sort Physical sorting analogy
Patience Sort Longest Increasing Subsequence applications
7. Sorting Algorithms Commonly Taught in Data Structures &
Algorithms
These are the core algorithms covered in most undergraduate courses and technical interviews:
1. Bubble Sort
2. Selection Sort
3. Insertion Sort
4. Merge Sort
Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 3/4
5. Quick Sort
6. Heap Sort
7. Shell Sort
8. Counting Sort
9. Radix Sort
10. Bucket Sort
11. Tree Sort
12. TimSort
13. IntroSort
Learning Roadmap
Level Algorithms
Beginner Bubble, Selection, Insertion
Intermediate Shell, Merge, Quick, Heap
Advanced Counting, Radix, Bucket, Tree
Expert TimSort, IntroSort, SmoothSort, GrailSort, PDQSort, Parallel Sorting, External Sorting
This progression moves from simple quadratic algorithms to efficient O(n log n) methods, then to
linear-time specialized sorts and modern production-grade algorithms.
Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 4/4