Sorting
Algorithms
Oluwabusola Adeleke
Senior Software Engineer
at E5 & Rad
Welcome to Class 11
What we will cover today
What is Sorting Algorithm?
Why learn different sorting algorithm?
Understand the types of sorting
Cover 17 sorting techniques
Q&A
What is Sorting?
❖ Arranging data in a specific order (ascending or descending)
❖ It is one of the most fundamental operations in computer
science
❖ It is used in many real-world applications:
➢ Phone contacts
➢ Library books
➢ Student records
➢ Shopping items by price
Why learn different sorting algorithms ?
❖ Different algorithms work better for
different situations
❖ Understanding trade-offs helps in choosing
the right algorithm
❖ Improves problem-solving skills
❖ Common topic in technical interviews
Types of Sorting Algorithm
❖Comparison sort
❖Non-comparison sort
Comparison Sort
❖Bubble Sort
➢ Simplest sorting algorithm
➢ Works by repeatedly swapping adjacent elements
➢ Like bubbles rising to the surface
➢ Best for: Small arrays or nearly sorted data
➢ Worst for: Large arrays or reverse sorted data
➢ Time Complexity: O(n²)
Comparison Sort
❖Insertion Sort
➢ Builds sorted array one element at a time
➢ Efficient for small data/nearly sorted arrays
➢ Like sorting playing cards in hand
➢ Best for: Online data (streaming inputs)
➢ Worst for: Large random datasets
➢ Time: O(n²)
Comparison Sort
❖Selection Sort
➢ Works by repeatedly finding minimum + swapping
➢ Like selecting shortest person in a line
➢ Best for: Memory-constrained environments
➢ Worst for: Any practical large datasets
➢ Time: O(n²)
Comparison Sort
❖Merge Sort
➢ Divide-and-conquer approach
➢ Works by splitting arrays → sorting → merging
➢ Like organizing a library shelf systematically
➢ Best for: Linked lists, external sorting
➢ Worst for: Memory-constrained systems
➢ Time: O(n log n)
Comparison Sort
❖Quick Sort
➢ Pivot-based partitioning
➢ Works by dividing array around pivot recursively
➢ Like organizing a messy desk quickly
➢ Best for: General-purpose sorting
➢ Worst: O(n²) for bad pivots (rare)
➢ Time: O(n log n) avg
Comparison Sort
❖Heap Sort
➢ Uses binary heap structure
➢ Works by building heap + extracting elements
➢ Like removing tallest trees first
➢ Best for: In-place sorting, Real-time systems
➢ Worst: Cache-sensitive system
➢ Time: O(n log n)
Comparison Sort
❖Shell Sort
➢ Generalized Insertion Sort
➢ Works by sorting elements with shrinking gaps
➢ Like coarse-to-fine sanding
➢ Best for: Medium-sized arrays
➢ Worst for: Bad gap sequences
➢ Time Complexity: O(n log n) to O(n²)
Comparison Sort
❖Tim Sort
➢ Hybrid (Merge + Insertion)
➢ Works by splitting data into runs + merging
➢ Like warehouse sorting optimization
➢ Best for: Real-world mixed data
➢ Worst for: Highly custom needs
➢ Time Complexity: O(n log n)
Comparison Sort
❖Cycle Sort
➢ Write-optimized algorithm
➢ Works by rotating elements into position
➢ Like rotating puzzle pieces
➢ Best for: Flash memory/SSDs
➢ Worst for: General-purpose use
➢ Time Complexity: O(n²)
Comparison Sort
❖Comb Sort
➢ Bubble Sort variant
➢ Works with shrinking gap (1.3 factor)
➢ Like removing "turtles" in early passes
➢ Best for: Moderate-sized arrays
➢ Worst for: Bad gap sequences
➢ Time Complexity: O(n²)
Comparison Sort
❖Gnome Sort
➢ Single-loop algorithm
➢ Works by swapping backward when needed
➢ Like a garden gnome sorting flower pots
➢ Best for: Simple implementations
➢ Worst for: Practical applications
➢ Time Complexity: O(n²)
Comparison Sort
❖Cocktail Sort
➢ Bidirectional Bubble Sort
➢ Works by alternating left-right passes
➢ Like shaking a cocktail mixer
➢ Best for: Moderate data with small ranges
➢ Worst for: Large random arrays
➢ Time Complexity: O(n²)
Comparison Sort
❖Bitonic Sort
➢ Parallel-friendly sort
➢ Works by building bitonic sequences
➢ Like mountain range peak sorting
➢ Best for: GPU/hardware implementations
➢ Worst for: Non-power-of-two data
➢ Time Complexity: O(n log²n)
Non-Comparison Sort
❖Radix Sort
➢ Sorts by digits/characters
➢ Best for: Fixed-size keys (numbers/strings)
➢ Time: O(nk) (k=key length)
Non-Comparison Sort
❖Bucket Sort
➢ Distributes elements into buckets
➢ Best for: Uniformly distributed data
➢ Time: O(n + k)
Non-Comparison Sort
❖Counting Sort
➢ Counts occurrences of values
➢ Best for: Small integer ranges
➢ Time: O(n + k) (k=value range)
Questions ???
What’s Next!!!
Class 12 – Data Structures - Arrays, Hash Tables, Linked Lists etc.
