Sorting Algorithms
Detail Explanation
With Animations
Telugu
Sorting Algorithms
Bubble Sort
Quick Sort
Merge Sort Selection Sort
Bucket Sort
Heap Sort Insertion Sort
Count Sort
Radix Sort
Bubble Sort 5 1 4 2 8
Bubble Sort
Bubble Sort is a simple comparison-based sorting algorithm
that repeatedly swaps adjacent elements if they are in the wrong
order. This process continues until the entire list is sorted.
Bubble Sort Working
How it Works?
Start from the first element and compare it with the next element.
If the first element is greater than the second, swap them.
Move to the next adjacent pair and repeat the process until the last
element.
The largest element bubbles up to the end after each complete pass.
Repeat the process for the remaining unsorted elements until the entire
list is sorted.
Example of Bubble Sort
Example of Bubble Sort
5 1 4 2 8
Example of Bubble Sort
Iteration 1:
5 1 4 2 8
Example of Bubble Sort
Iteration 1:
5 1
4 2 8
Example of Bubble Sort
Iteration 1:
1 5
4 2 8
Example of Bubble Sort
Iteration 1:
1 5 4 2 8
Example of Bubble Sort
Iteration 1:
5 4
1 2 8
Example of Bubble Sort
Iteration 1:
4 5
1 2 8
Example of Bubble Sort
Iteration 1:
1 4 5 2 8
Example of Bubble Sort
Iteration 1:
5 2
1 4 8
Example of Bubble Sort
Iteration 1:
2 5
1 4 8
Example of Bubble Sort
Iteration 1:
1 4 2 5 8
Example of Bubble Sort
Iteration 1:
5 8
1 4 2
Example of Bubble Sort
Iteration 1:
1 4 2 5 8
Example of Bubble Sort
Iteration 2:
1 4
2 5 8
Example of Bubble Sort
Iteration 2:
1 4 2 5 8
Example of Bubble Sort
Iteration 2:
4 2
1 5 8
Example of Bubble Sort
Iteration 2:
2 4
1 5 8
Example of Bubble Sort
Iteration 2:
1 2 4 5 8
Example of Bubble Sort
Sorted Array
1 2 4 5 8
Key Characteristics
✅ Time Complexity:
Worst & Average Case: O(n²) (when the list is in reverse order).
Best Case: O(n) (when the list is already sorted).
✅ Stable Sort: Maintains the relative order of equal elements.
❌ Inefficient for Large Data Sets: Due to O(n²) complexity.
✅ Simple & Easy to Implement: Good for small lists or educational
purposes.
Selection Sort 29 10 14 37 13
Selection Sort
Selection Sort is a comparison-based sorting algorithm that divides the
array into two parts:
1. Sorted part (gradually built from the left).
2. Unsorted part (initially contains all elements).
The algorithm repeatedly selects the smallest element from the unsorted
part and swaps it with the first unsorted element.
Selection Sort Working
How it Works?
Find the Minimum Element in the unsorted part.
Swap it with the first element of the unsorted part.
Move the boundary between sorted and unsorted sections one step
forward.
Repeat until the entire list is sorted.
Selection Sort Example
Selection Sort
Find Smallest & Swap with First Position
29 10 14 37 13
Selection Sort
Find Smallest & Swap with First Position
29 10 14 37 13
Selection Sort
Find Smallest & Swap with First Position
10 29 14 37 13
Selection Sort
Find Smallest & Swap with Second Position
10 29 14 37 13
Selection Sort
Find Smallest & Swap with Second Position
10 13 14 37 29
Selection Sort
Find Smallest & Swap with Third Position
10 13 14 37 29
Selection Sort
Find Smallest & Swap with Fourth Position
10 13 14 37 29
Selection Sort
Find Smallest & Swap with Fourth Position
10 13 14 29 37
Selection Sort
Sorted Elements
10 13 14 29 37
Key Characteristics
✅ Time Complexity:
Worst & Average Case: O(n²) (Always compares every element).
Best Case: O(n²) (Even if sorted, still does full comparisons).
✅ In-Place Sorting Algorithm: Uses constant space O(1).
✅ Not Stable: Order of equal elements may change.
✅ Good for Small Arrays: Performs well for small datasets but
inefficient for large ones.
Insertion Sort 8 4 3 7 6
Insertion Sort
Insertion Sort is a simple and efficient sorting algorithm that builds the
final sorted array one item at a time. It works by taking each element and
inserting it into its correct position in the sorted part of the array.
Insertion Sort Working
How it Works?
Start from the second element (since a single element is already sorted).
Compare it with previous elements and shift larger elements to the right.
Insert the current element into the correct position.
Repeat the process for all elements.
Insertion Sort Example
Insertion Sort
8 4 3 7 6
Insertion Sort
Step-by-Step Sorting Process
1st Pass (Insert 4 into Sorted Position in [8])
Compare 4 with 8, shift 8 to the right.
Insert 4 at the correct position.
8 4 3 7 6
Insertion Sort
Step-by-Step Sorting Process
1st Pass (Insert 4 into Sorted Position in [8])
Compare 4 with 8, shift 8 to the right.
Insert 4 at the correct position.
4 8 3 7 6
Insertion Sort
Step-by-Step Sorting Process
2nd Pass (Insert 3 into Sorted Position in [4, 8])
Compare 3 with 8 → shift 8 right.
Compare 3 with 4 → shift 4 right.
Insert 3 at the correct position.
4 8 3 7 6
Insertion Sort
Step-by-Step Sorting Process
2nd Pass (Insert 3 into Sorted Position in [4, 8])
Compare 3 with 8 → shift 8 right.
Compare 3 with 4 → shift 4 right.
Insert 3 at the correct position.
4 3 8 7 6
Insertion Sort
Step-by-Step Sorting Process
2nd Pass (Insert 3 into Sorted Position in [4, 8])
Compare 3 with 8 → shift 8 right.
Compare 3 with 4 → shift 4 right.
Insert 3 at the correct position.
3 4 8 7 6
Insertion Sort
Step-by-Step Sorting Process
3rd Pass (Insert 7 into Sorted Position in [3, 4, 8])
Compare 7 with 8 → shift 8 right.
Insert 7 at the correct position.
3 4 8 7 6
Insertion Sort
Step-by-Step Sorting Process
3rd Pass (Insert 7 into Sorted Position in [3, 4, 8])
Compare 7 with 8 → shift 8 right.
Insert 7 at the correct position.
3 4 7 8 6
Insertion Sort
4th Pass (Insert 6 into Sorted Position in [3, 4, 7, 8])
Compare 6 with 8 → shift 8 right.
Compare 6 with 7 → shift 7 right.
Insert 6 at the correct position.
3 4 7 8 6
Insertion Sort
4th Pass (Insert 6 into Sorted Position in [3, 4, 7, 8])
Compare 6 with 8 → shift 8 right.
Compare 6 with 7 → shift 7 right.
Insert 6 at the correct position.
3 4 7 6 8
Insertion Sort
4th Pass (Insert 6 into Sorted Position in [3, 4, 7, 8])
Compare 6 with 8 → shift 8 right.
Compare 6 with 7 → shift 7 right.
Insert 6 at the correct position.
3 4 6 7 8
Key Characteristics
✅ Time Complexity:
Worst & Average Case: O(n²) (When the list is in reverse order).
Best Case: O(n) (When the list is already sorted).
✅ Stable Sort: Maintains the relative order of equal elements.
✅ In-Place Sorting Algorithm: Uses constant space O(1).
✅ Efficient for Small and Nearly Sorted Lists: Used in real-world
applications like handwritten sorting, card sorting, and online
sorting systems.
Merge Sort
38 27 43 3 9 82 10
Merge Sort
Merge Sort is a divide-and-conquer sorting algorithm that recursively
divides the array into two halves, sorts them separately, and merges the
sorted halves to get the final sorted array
Merge Sort Working
How it Works?
Divide: Split the array into two equal halves until each sub-array
contains only one element.
Conquer: Recursively sort each half.
Merge: Combine the two sorted halves into a single sorted array.
Merge Sort Example
Merge Sort
Step-by-Step Sorting Process
Step 1: Divide the Array
38 27 43 3 9 82 10
Merge Sort
Step-by-Step Sorting Process
Step 1: Divide the Array
38 27 43 3 9 82 10
Merge Sort
Step-by-Step Sorting Process
Step 2: Further Divide Until Single Elements
38 27 43 3 9 82 10
Merge Sort
Step-by-Step Sorting Process
Step 2: Further Divide Until Single Elements
38 27 43 3 9 82 10
Merge Sort
Step-by-Step Sorting Process
Step 2: Further Divide Until Single Elements
38 27 43 3 9 82 10
Merge Sort
Step-by-Step Sorting Process
Step 3: Merge Sorted Parts
38 27 43 3 9 10 82
Merge Sort
Step-by-Step Sorting Process
Step 3: Merge Sorted Parts
27 38 43 3 9 10 82
Merge Sort
Final Sorted Array
3 9 10 27 38 43 82
Key Characteristics
✅ Time Complexity:
Worst, Average, and Best Case: O(n log n) (Consistent
performance).
✅ Stable Sort: Maintains the relative order of equal elements.
✅ Not In-Place: Uses extra space O(n) for merging.
✅ Efficient for Large Data Sets: Often used in external sorting
(e.g., sorting files on disk).
Quick Sort
10 80 30 90 40 50 70
Quick Sort
Quick Sort is a divide-and-conquer sorting algorithm that selects a pivot
element, partitions the array into smaller and larger elements, and
recursively sorts the subarrays.
Quick Sort Working
How it Works?
Choose a Pivot Element (can be first, last, middle, or random).
Partition the Array: Rearrange elements so that:
Elements smaller than the pivot go to the left.
Elements larger than the pivot go to the right.
Recursively Apply Quick Sort on left and right subarrays.
Combine the sorted subarrays to get the final sorted array.
Quick Sort Example
Quick Sort
Unsorted Array: [10, 80, 30, 90, 40, 50, 70]
10 80 30 90 40 50 70
Quick Sort
Step-by-Step Sorting Process
Step 1: Choose a Pivot (Last Element)
Pivot = 70
Partition the array: Move elements smaller than 70 to the left, and
greater to the right.
Result after partitioning: [10, 30, 40, 50, 70, 90, 80]
Pivot 70 is now in its correct position.
10 80 30 90 40 50 70
Quick Sort
Step-by-Step Sorting Process
Step 1: Choose a Pivot (Last Element)
Pivot = 70
Partition the array: Move elements smaller than 70 to the left, and
greater to the right.
Result after partitioning: [10, 30, 40, 50, 70, 90, 80]
Pivot 70 is now in its correct position.
10 30 40 50 70 90 80
Quick Sort
Step-by-Step Sorting Process
Step 2: Recursively Apply Quick Sort on Left Subarray [10, 30, 40, 50]
Pivot = 50
Partition: [10, 30, 40, 50] → [10, 30, 40, 50] (Already sorted).
10 30 40 50 70 90 80
Quick Sort
Step-by-Step Sorting Process
Step 2: Recursively Apply Quick Sort on Left Subarray [10, 30, 40, 50]
Pivot = 50
Partition: [10, 30, 40, 50] → [10, 30, 40, 50] (Already sorted).
10 30 40 50 70 90 80
Quick Sort
Step-by-Step Sorting Process
Step 2: Recursively Apply Quick Sort on Left Subarray [10, 30, 40, 50]
Pivot = 50
Partition: [10, 30, 40, 50] → [10, 30, 40, 50] (Already sorted).
10 30 40 50 70 90 80
Quick Sort
Step-by-Step Sorting Process
Step 3: Recursively Apply Quick Sort on Right Subarray [90, 80]
Pivot = 80
Partition: [80, 90]
10 30 40 50 70 90 80
Quick Sort
Step-by-Step Sorting Process
Step 3: Recursively Apply Quick Sort on Right Subarray [90, 80]
Pivot = 80
Partition: [80, 90]
10 30 40 50 70 80 90
Quick Sort
Final Sorted Array: [10, 30, 40, 50, 70, 80, 90]
10 30 40 50 70 80 90
Key Characteristics
✅ Time Complexity:
Best & Average Case: O(n log n) (Efficient for large datasets).
Worst Case: O(n²) (If pivot selection is poor, e.g., sorted or
reverse-sorted array).
✅ In-Place Sorting Algorithm: Uses O(log n) extra space
(recursive calls).
✅ Not Stable: Relative order of equal elements may change.
✅ Used in Real Applications: It is one of the fastest sorting
algorithms used in databases, search engines, and high-
performance systems.
Count Sort
4 2 2 8 3 3 1
Count Sort
Counting Sort is a non-comparative sorting algorithm that counts the
occurrences of each element and uses this information to place elements
in the correct order. It is efficient for sorting numbers within a limited
range.
Count Sort Working
How it Works?
Find the maximum value in the array.
Create a count array to store the frequency of each element.
Compute cumulative counts to determine the correct positions.
Place elements into the output array using cumulative counts.
Copy the sorted elements back into the original array.
Count Sort Example
Count Sort
Unsorted Array: [4, 2, 2, 8, 3, 3, 1]
4 2 2 8 3 3 1
Count Sort
Unsorted Array: [4, 2, 2, 8, 3, 3, 1]
4 2 2 8 3 3 1
1 2 3 4 5 6 7 8 9
Count Sort
Unsorted Array: [4, 2, 2, 8, 3, 3, 1]
2 2 8 3 3 1
1 2 3 4 5 6 7 8 9
Count Sort
Unsorted Array: [4, 2, 2, 8, 3, 3, 1]
2 8 3 3 1
1 2 3 4 5 6 7 8 9
Count Sort
Unsorted Array: [4, 2, 2, 8, 3, 3, 1]
8 3 3 1
1 2 3 4 5 6 7 8 9
Count Sort
Unsorted Array: [4, 2, 2, 8, 3, 3, 1]
3 3 1
1 2 3 4 5 6 7 8 9
Count Sort
Unsorted Array: [4, 2, 2, 8, 3, 3, 1]
3 1
1 2 3 4 5 6 7 8 9
Count Sort
Unsorted Array: [4, 2, 2, 8, 3, 3, 1]
1 2 3 4 5 6 7 8 9
Count Sort
Unsorted Array: [4, 2, 2, 8, 3, 3, 1]
1 2 3 4 5 6 7 8 9
Count Sort
Sorted Array: [1, 2, 2, 3, 3, 4, 8]
1 2 2 3 3 4 8
1 2 3 4 5 6 7 8 9
Key Characteristics
✅ Time Complexity:
Best, Average, and Worst Case: O(n + k) (where n is the number of
elements, k is the range of values).
✅ Space Complexity: O(k) (Extra space needed for count array).
✅ Stable Sort: Maintains the relative order of equal elements.
✅ Efficient for Small Integer Ranges: Used when elements are
within a small, fixed range (e.g., age sorting, exam scores).
5
1
Bucket Sort
4
8
Bucket Sort
Bucket Sort is a distribution-based sorting algorithm that divides
elements into multiple buckets and sorts each bucket individually using
another sorting algorithm (like Insertion Sort or Quick Sort).
Bucket Sort Working
How it Works?
Find the range of elements (minimum and maximum values).
Divide the range into equal-sized buckets.
Distribute elements into these buckets based on their values.
Sort each bucket individually using another sorting algorithm.
Concatenate all sorted buckets to get the final sorted array.
Bucket Sort Example
Bucket Sort
8 6 2 4 7 5 1 3
Bucket Sort
8 6 2 4 7 5 1 3
Step 1: Create Buckets
Since all numbers are between 0 and 1, create n
buckets (one for each element).
Bucket Sort
Step 1: Create Buckets
Since all numbers are between 0 and 1, create n buckets (one for each element).
8 6 2 4 7 5 1 3
1-3 4-6 7-9
Bucket Sort
Step 2: Distribute Elements into Buckets
8 6 2 4 7 5 1 3
1-3 4-6 7-9
Bucket Sort
Step 2: Distribute Elements into Buckets
3 5
1 4 7
2 6 8
1-3 4-6 7-9
Bucket Sort
Step 3: Sort Each Bucket
Each bucket is sorted individually (using Insertion Sort or another
sorting method).
1 4
2 5 7
3 6 8
1-3 4-6 7-9
Bucket Sort
Step 4: Concatenate All Sorted Buckets
1 4
2 5 7
3 6 8
1-3 4-6 7-9
Bucket Sort
Step 4: Concatenate All Sorted Buckets
1 2 3 4 5 6 7 8
Key Characteristics
✅ Time Complexity:
Best Case: O(n + k) (When data is uniformly distributed).
Worst Case: O(n²) (If all elements land in one bucket and use a
slow sorting algorithm).
✅ Space Complexity: O(n + k) (Extra space for buckets).
✅ Stable Sort: Can maintain order if sorting within buckets is
stable.
✅ Efficient for Uniformly Distributed Data: Often used for
floating-point numbers, percentages, and data with limited range.
Radix Sort
170 45 75 90 802 24 2 66
Radix Sort
Radix Sort is a non-comparative sorting algorithm that sorts numbers
digit by digit, starting from the least significant digit (LSD) to the most
significant digit (MSD). It is useful for sorting integers and strings
efficiently.
Radix Sort Working
How it Works?
Find the maximum number in the array to determine the number of
digits.
Sort the numbers digit by digit, starting from the least significant digit
(LSD) to the most significant digit (MSD).
Use a stable sorting algorithm (like Counting Sort) to sort numbers
based on each digit.
Repeat the process for each digit until all digits are processed.
Radix Sort Example
Radix Sort Example
170 45 75 90 802 24 2 66
Radix Sort Example
1. Sort by Least Significant Digit (Unit Place)
Consider only the rightmost digit and sort using Counting Sort
170 45 75 90 802 24 2 66
0 1 2 3 4 5 6 7 8 9
Radix Sort Example
1. Sort by Least Significant Digit (Unit Place)
Consider only the rightmost digit and sort using Counting Sort
90 802 75
170 2 24 45 66
0 1 2 3 4 5 6 7 8 9
Radix Sort Example
1. Sort by Least Significant Digit (Unit Place)
Consider only the rightmost digit and sort using Counting Sort
170 90 802 2 24 45 75 66
0 1 2 3 4 5 6 7 8 9
Radix Sort Example
2. Sort by Tens Place
Consider the second last digit and sort:
170 90 802 2 24 45 75 66
0 1 2 3 4 5 6 7 8 9
Radix Sort Example
2. Sort by Tens Place
Consider the second last digit and sort:
802 75
2 24 45 66 170 90
0 1 2 3 4 5 6 7 8 9
Radix Sort Example
2. Sort by Tens Place
Consider the second last digit and sort:
802 2 24 45 66 75 170 90
0 1 2 3 4 5 6 7 8 9
Radix Sort Example
3. Sort by Hundreds Place
Consider the third last digit and sort:
802 2 24 45 66 75 170 90
0 1 2 3 4 5 6 7 8 9
Radix Sort Example
3. Sort by Hundreds Place
Consider the third last digit and sort:
2 170 24 45 66 75 802 90
0 1 2 3 4 5 6 7 8 9
Radix Sort Example
3. Sort by Hundreds Place
Consider the third last digit and sort:
2 24 45 66 75 90 170 802
0 1 2 3 4 5 6 7 8 9
Key Characteristics
✅ Time Complexity:
Best, Average, and Worst Case: O(nk) (where n is the number of
elements, k is the number of digits).
✅ Space Complexity: O(n + k) (Extra space for Counting Sort).
✅ Stable Sort: Preserves the relative order of equal elements.
✅ Efficient for Large Integers & Fixed-Length Strings: Used in
phone numbers, zip codes, and serial numbers.
10
Heap Sort
5 3
4 10 3 5 1
4 1
Heap Sort
Heap Sort works by first converting an array into a heap (max-heap or
min-heap) and then repeatedly extracting the largest (or smallest) element
from the heap and placing it in the correct position.
Heap Sort Working
How it Works?
Build a Max Heap: Convert the array into a binary max heap (where the
parent node is always greater than its child nodes).
Extract Maximum Element: Swap the root (largest element) with the
last element and reduce the heap size.
Heapify the Remaining Elements: Restore the max heap property.
Repeat Until Sorted: Keep extracting the maximum element and placing
it in the sorted portion of the array.
Heap Sort Example
Heap Sort
4 10 3 5 1
Heap Sort
Build max heap
4 10 3 5 1
Convert the array into a max heap where each parent node is greater
than its child nodes.
Heap Sort
Build max heap
10
4 10 3 5 1
5 3
4 1
Heap Sort
Extract the Maximum Element (Root) and Swap with Last Element:
Swap 10 (root) with 1 (last element): [1, 5, 3, 4, 10]
1
[1, 5, 3, 4,10] 5 3
[1, 5, 3, 4]
4 10
Heap Sort
Extract the Maximum Element (Root) and Swap with Last Element:
Swap 10 (root) with 1 (last element): [1, 5, 3, 4, 10]
Remove 10 from the heap and heapify [1, 5, 3, 4]. 1
[1, 5, 3, 4,10] 5 3
[1, 5, 3, 4]
4
Heap Sort
1. Rebuild the heap with [1,5,3,4]
5
4 3
1
Heap Sort
1. Rebuild the heap with [1,5,3,4]
2. Swap 5 (root) with 1 (last element): [1, 4, 3, 5, 10]
1
Remove 5 from the heap and heapify [1, 4, 3].
4 3
[1, 4, 3]
5
Heap Sort
1. Rebuild the heap with [1,4,3] 4
1
Heap Sort
1. Rebuild the heap with [1,4,3]
2. Swap 4 (root) with 1 (last element): [3, 1, 4, 5, 10]
Remove 4 from the heap and heapify [ 3,1]. 1
3
[3,1]
4
Heap Sort
1. Rebuild the heap with [3,1]
3
1
Heap Sort
1. Rebuild the heap with [3,1]
2. Swap 3 (root) with 1 (last element): [ 1,3, 4, 5, 10]
3
1
Heap Sort
Final Sorted Array [ 1,3, 4, 5, 10]
1 3 4 5 10
Key Characteristics
✅ Time Complexity: O(n log n) for all cases (best, average, and
worst).
✅ In-Place Sort: Does not require additional storage.
❌ Not Stable: Relative order of equal elements may change.
✅ Used for Priority Queues: Efficient for scheduling tasks.
THANK YOU