Analysis of Sorting Algorithms
Algorithm Analysis Overview
• Algorithm analysis determines efficiency using
input size n.
• Three cases: Best, Average, and Worst.
• Asymptotic notations:
• - Big-O: Upper bound (Worst case)
• - Theta (Θ): Tight bound (Average case)
• - Omega (Ω): Lower bound (Best case)
Merge Sort – Concept
• Divide and Conquer algorithm.
• Divides array into halves, sorts each half
recursively, merges sorted halves.
• Stable sorting algorithm.
Merge Sort – Recurrence and
Analysis
• Recurrence: T(n) = 2T(n/2) + O(n)
• Applying Master Theorem:
• a = 2, b = 2, f(n) = O(n)
• => T(n) = O(n log n)
• Best Case: Ω(n log n)
• Average Case: Θ(n log n)
• Worst Case: O(n log n)
• Space Complexity: O(n)
Quick Sort – Concept
• Divide and Conquer algorithm.
• Selects a pivot element, partitions the array
around pivot.
• Recursively sorts subarrays before and after
pivot.
• Not a stable algorithm.
Quick Sort – Time Complexity
Analysis
• Best Case: Pivot divides array evenly.
• T(n) = 2T(n/2) + O(n) → O(n log n)
• Average Case: Expected O(n log n)
• Worst Case: Pivot is smallest/largest element
each time.
• T(n) = T(n-1) + O(n) → O(n²)
• Space Complexity: O(log n) (recursive stack)
Quick Sort – Optimization
Techniques
• Randomized pivot selection reduces chance of
worst case.
• Median-of-three pivot improves performance
on sorted input.
• Hybrid approach (switch to Insertion Sort for
small subarrays).
Heap Sort – Concept
• Based on Binary Heap data structure
(Complete Binary Tree).
• Max-Heap: Parent ≥ Children.
• Steps:
• 1. Build a max heap.
• 2. Swap root (max) with last element.
• 3. Heapify reduced heap.
Heap Sort – Analysis
• Building heap: O(n).
• Each heapify: O(log n).
• Total: O(n log n).
• Best Case: Ω(n log n)
• Average Case: Θ(n log n)
• Worst Case: O(n log n)
• Space Complexity: O(1)
• Not stable.
Comparison Summary
• Merge Sort: O(n log n) for all cases, Stable,
Needs extra memory.
• Quick Sort: O(n log n) average, O(n²) worst,
Not stable, In-place.
• Heap Sort: O(n log n) all cases, Not stable, In-
place.
• Merge Sort often used for linked lists; Quick
Sort for arrays.