Merge Sort and Bubble Sort Complexities
Filed under TCS · Also reported at Wipro
Free read 2 of 3Explain Bubble Sort. Best case: O(n) when already sorted (with optimized flag). Worst/Average case: O(n^2). Space complexity: O(1).
The question
Discuss Merge Sort and Bubble Sort algorithms, detailing their time and space complexities in best, average, and worst cases.
Constraints
- Cover both sorting algorithms thoroughly.
- Explicitly state best, average, and worst-case time complexities and space complexities.
Approach
Explain Bubble Sort. Best case: O(n) when already sorted (with optimized flag). Worst/Average case: O(n^2). Space complexity: O(1).
Explain Merge Sort (Divide and Conquer). Best, average, and worst-case time complexities are all O(n log n). Space complexity: O(n) for temporary arrays.
Compare stability and memory footprints: Merge sort is stable and uses extra space, whereas Bubble sort is an in-place, stable sort with poor time scaling.
Tips
- What they are testing: Interviewers look for precise asymptotic analysis and understanding of why divide-and-conquer algorithms outperform naive ones.
- Common mistake: Confusing the O(n) best-case time complexity of an optimized bubble sort with merge sort's consistent O(n log n).
Related TCS questions
Collected from public candidate posts and coding forums. Updated Nov 2026.