CoreSource checked

Bubble Sort

Sorts a list by repeatedly swapping neighboring items that are out of order.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Sorting
Difficulty: Beginner
Family: Exchange Sort
Tier: Core
Status: Verified
Review: Source Checked
Sources: 1
Formulas: 0
Relationships: 2
Code example: Ready
Visualization: Ready
Aliases: Sinking Sort

Overview

Bubble Sort walks through the list many times, moving larger values toward the end one swap at a time.

Core Concepts

comparison rulein-place updatestable orderingexchange sortordering invariantcomparison or key rulearray rearrangement

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(n)

Average

O(n^2)

Worst

O(n^2)

Space

O(1)

When to Use

Use Bubble Sort when you need to compare adjacent values.
Use it for teaching sorting basics with inputs like array or list of comparable values.
Use it when ordered output makes later searching, ranking, or presentation easier.
Use it when the Exchange Sort tradeoff is acceptable for the problem size.

When Not to Use

Avoid it when a partial order, top-k result, or streaming approach would answer the question with less work.
Avoid it when O(n^2) worst-case behavior is too costly for the expected input size.
Avoid it when the required output is not sorted array or list.

What It Does

Compares adjacent values
Swaps values until the list is ordered

Use Cases

Teaching sorting basics
Sorting very small lists
Demonstrating swap-based sorting

Inputs

Array or list of comparable values

Outputs

Sorted array or list

Pseudocode

1.Start at the beginning of the list
2.Compare each pair of neighboring values
3.Swap the pair if it is out of order
4.Repeat passes until a full pass makes no swaps

Canonical Example

Input: values = [5, 1, 4, 2]
Output: values = [1, 2, 4, 5]
Explanation: Bubble Sort: The algorithm reorders the values so later operations can read them in ascending order.

Implementation Notes

Keep the input contract explicit: Array or list of comparable values.
Use this step as the implementation spine: Start at the beginning of the list.
Then preserve the next state change: Compare each pair of neighboring values.
Test with empty input, one item, duplicates, and already sorted values.

Common Pitfalls

Bubble Sort is easy to understand but rarely chosen for real workloads.
Assuming stability without checking the implementation can reorder equal keys.
Forgetting to define how equal values and custom comparison rules should behave.
Returning sorted array or list without handling empty, invalid, or boundary inputs.

Interactive Mechanism Walkthrough

Array Partition & Ordering Trace

Show adjacent items swapping while larger values drift to the end.

[0]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

Step 1 of 4: Start at the beginning of the list

array-sort

Notes

Bubble Sort operates in O(n^2) time and O(1) space within the Exchange Sort family. Often compared with Insertion Sort and Selection Sort.

Sources (1)

What each reference supports for this entry.

Introduction to Algorithms (CLRS)

Book

Textbook support for Bubble Sort invariants, recurrences, relaxation rules, or asymptotic analysis.

Open source

Explore Next

Good next jumps from the relationship graph, ranked for useful discovery.

Open discovery Open map

Alternative toInsertion Sort

Sorting · Foundation

Bubble sort and insertion sort are simple stable quadratic sorts with different local-movement behavior.

Compare with this

AlternativesSelection Sort

Sorting · Core

Selection sort reduces swaps compared with bubble sort while keeping quadratic comparison cost.