---
title: "Best, average, worst case of sorts"
subject: "Data Structure and Algorithm"
chapter: 7
key: "semester_4/data_structure_and_algorithm:sorting-cases-big-oh"
source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/sorting-cases-big-oh
site: BCT Engineering
---

# Best, average, worst case of sorts

Data Structure and Algorithm · Chapter 7: Sorting

- Asked in: 2073 Bhadra, 2 marks
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/sorting-cases-big-oh
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-7

## Question

Provide best case, average case and worst case for the following algorithms in Big-Oh: bubble sort, insertion sort, merge sort and selection sort.

## Short answer

Bubble sort: O(n) best (with flag), O(n^2) average/worst. Insertion sort: O(n) best, O(n^2) average/worst. Merge sort: O(n log n) all cases. Selection sort: O(n^2) all cases.

## Answer

| Algorithm | Best case | Average case | Worst case |
|---|---|---|---|
| Bubble sort | O(n) (with swap-flag, already sorted) | O(n²) | O(n²) |
| Insertion sort | O(n) (already sorted) | O(n²) | O(n²) (reverse order) |
| Merge sort | O(n log n) | O(n log n) | O(n log n) |
| Selection sort | O(n²) | O(n²) | O(n²) |

Without the early-exit flag, bubble sort is O(n²) even in the best case. Selection sort always scans the full unsorted part, so it never improves. Merge sort halves the list each time (log n levels) and merges in O(n) per level.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What are best, average and worst cases of selection sort?
   A. O(n), O(n^2), O(n^2)
   B. O(n^2) in all three
   C. O(n log n) in all
   D. O(n), O(n), O(n^2)
   Answer: B. It always scans the full unsorted part. (Key point: Selection)

2. When is insertion sort O(n)?
   A. Reverse-order input
   B. Already sorted input
   C. Random input
   D. Never
   Answer: B. Each element needs only one comparison. (Key point: Insertion best)

3. Why is merge sort O(n log n) in all cases?
   A. It halves the list (log n levels) and merges in O(n) per level
   B. It uses a flag
   C. It picks the median
   D. It compares only adjacent items
   Answer: A. Split depth is log n; the merge cost does not depend on input order. (Key point: Merge sort)

## Related in Data Structure and Algorithm

- [Big-Oh significance and limitation](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Abig-oh-significance-limitation) — Data Structure and Algorithm, chapter 9
- [Merge sort on 85, 76, 46, 92, ...](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Amerge-sort-trace-85-76) — Data Structure and Algorithm, chapter 7
- [Merge sort algorithm and trace](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Amerge-sort-algorithm-trace) — Data Structure and Algorithm, chapter 7
- [Merge and radix sort on 142, 523, ...](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Amerge-radix-trace-142) — Data Structure and Algorithm, chapter 7
- [Merge sort on 47, 27, 56, 23, ...](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Amerge-sort-trace-47-27) — Data Structure and Algorithm, chapter 7
- [Heap tree insertion and heap sort](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aheap-insertion-and-sort) — Data Structure and Algorithm, chapter 7

## Related in other subjects

- [Correct program: case array and average](https://www.bctengineer.com/question.md?key=semester_1%2Fcomputer_programming%3Acorrect-program-case-array) — Computer Programming, chapter 3
- [Case study: feasibility, drawbacks, convincing](https://www.bctengineer.com/question.md?key=semester_5%2Finstrumentation_ii%3Acs-2072kartik-feasibility) — Instrumentation II, chapter 10
- [Sort employee structures by salary](https://www.bctengineer.com/question.md?key=semester_1%2Fcomputer_programming%3Astruct-employee-sort-salary) — Computer Programming, chapter 8, asked 2×
- [Microprocessors in instrumentation systems (case study)](https://www.bctengineer.com/question.md?key=semester_5%2Finstrumentation_ii%3Ambi-casestudy-statement) — Instrumentation II, chapter 1