Sorting Algorithms: From Bubble Sort to Efficient Sorting

Imagine you have this list:

[42, 7, 19, 3, 25, 11]

You want:

[3, 7, 11, 19, 25, 42]

That process is called sorting.

Sorting is one of the most fundamental operations in computer science. It appears everywhere:

• Databases
• Search engines
• E-commerce
• Operating systems
• Data analysis
• Machine learning
• Ranking systems
• Leaderboards
• Recommendation systems
• File management
• Scheduling

Learning sorting algorithms isn't just about putting numbers in ascending order.

It teaches some of the most important ideas in algorithm design:

Comparison, iteration, divide and conquer, swapping, recursion, optimization, and complexity analysis.

In this article, we'll build the foundation for understanding the major sorting algorithms.

What Is a Sorting Algorithm?

A sorting algorithm rearranges elements into a particular order.

For example:

Ascending

[8, 3, 5, 1, 9]

↓

[1, 3, 5, 8, 9]

Descending

[8, 3, 5, 1, 9]

↓

[9, 8, 5, 3, 1]

Sorting doesn't necessarily have to involve numbers.

We can sort:

Names
Products
Users
Dates
Prices
Scores
Objects
Files

For example:

["Rahul", "Aman", "Zoya", "Karan"]

can become:

["Aman", "Karan", "Rahul", "Zoya"]

Why Is Sorting Important?

Sorting can make other operations much easier.

Remember Binary Search from the previous article?

Binary Search requires an ordered search space.

For example:

[10, 20, 30, 40, 50, 60]

Because the data is sorted, we can efficiently eliminate half the search space.

Without ordering:

[40, 10, 60, 20, 50, 30]

Binary Search cannot be directly applied.

So sorting can be a preprocessing step that enables faster algorithms later.

The Major Sorting Algorithms

There are many sorting algorithms.

The important ones include:

Simple Sorting Algorithms

• Bubble Sort
• Selection Sort
• Insertion Sort

Efficient Comparison Sorts

• Merge Sort
• Quick Sort
• Heap Sort

Non-Comparison Sorting

• Counting Sort
• Radix Sort
• Bucket Sort

Each has different strengths and weaknesses.

Sorting Algorithm Complexity

Here's a useful overview:

* Optimized Bubble Sort can achieve O(n) on already sorted input.

** Typical recursive stack usage; implementation details matter.

Don't try to memorize everything yet.

We'll understand each algorithm individually.

Part 1: Bubble Sort

Let's begin with the simplest.

Bubble Sort

Bubble Sort repeatedly compares neighboring elements.

If they're in the wrong order, we swap them.

The largest unsorted element gradually moves toward the end.

It looks like the larger elements are bubbling upward toward their final positions.

Bubble Sort Example

Consider:

[5, 3, 8, 4, 2]

We compare:

5 and 3

Since:

5 > 3

swap them:

[3, 5, 8, 4, 2]

Next:

5 and 8

Already correct:

[3, 5, 8, 4, 2]

Next:

8 and 4

Swap:

[3, 5, 4, 8, 2]

Next:

8 and 2

Swap:

[3, 5, 4, 2, 8]

Now the largest element, 8, has reached the end.

First Pass

Starting with:

[5, 3, 8, 4, 2]

After one complete pass:

[3, 5, 4, 2, 8]

Notice:

8

is now in its final position.

The next pass doesn't need to consider it.

Second Pass

Start:

[3, 5, 4, 2, 8]

Compare:

3 and 5 → No swap
5 and 4 → Swap
4 and 2 → Swap

Result:

[3, 4, 2, 5, 8]

Now 5 is also in its final position.

Third Pass

[3, 4, 2, 5, 8]

Compare:

3 and 4 → No swap
4 and 2 → Swap

Result:

[3, 2, 4, 5, 8]

Fourth Pass

[3, 2, 4, 5, 8]

Compare:

3 and 2 → Swap

Result:

[2, 3, 4, 5, 8]

Sorted.

Bubble Sort Pseudocode

FOR i = 0 TO n - 1

    FOR j = 0 TO n - i - 2

        IF array[j] > array[j + 1]

            SWAP array[j] and array[j + 1]

        END IF

    END FOR

END FOR

The key idea:

Compare neighbors
        ↓
Swap if necessary
        ↓
Largest unsorted element moves right
        ↓
Repeat

Bubble Sort in Python

def bubble_sort(numbers):

    n = len(numbers)

    for i in range(n):

        for j in range(0, n - i - 1):

            if numbers[j] > numbers[j + 1]:
                numbers[j], numbers[j + 1] = numbers[j], numbers[j + 1]

    return numbers

Example:

numbers = [5, 3, 8, 4, 2]

print(bubble_sort(numbers))

Output:

[2, 3, 4, 5, 8]

Bubble Sort Complexity

There are nested loops.

Therefore, the typical complexity is:

O(n²)

For example, with:

n = 1,000

we can end up doing roughly millions of comparisons.

That's why Bubble Sort isn't normally the right choice for large datasets.

Optimizing Bubble Sort

We can make a small but important improvement.

What if the array is already sorted?

[1, 2, 3, 4, 5]

We don't need to keep making unnecessary passes.

We can track whether a swap happened.

def bubble_sort(numbers):

    n = len(numbers)

    for i in range(n):

        swapped = False

        for j in range(0, n - i - 1):

            if numbers[j] > numbers[j + 1]:

                numbers[j], numbers[j + 1] = numbers[j + 1], numbers[j]
                swapped = True

        if not swapped:
            break

    return numbers

If no swaps occur during a pass, the array is already sorted.

For an already sorted array, this optimized version can run in:

O(n)

Best case:

O(n)

Worst case:

O(n²)

Part 2: Selection Sort

Selection Sort takes a different approach.

Instead of repeatedly swapping neighbors, we:

Find the smallest element and put it in the correct position.

Consider:

[5, 3, 8, 4, 2]

Find the smallest:

2

Move it to the beginning:

[2, 3, 8, 4, 5]

Now ignore the first element.

Find the smallest in:

[3, 8, 4, 5]

It's:

3

Already in position.

Next:

[8, 4, 5]

Smallest:

4

Result:

[2, 3, 4, 8, 5]

Continue:

[2, 3, 4, 5, 8]

Sorted.

Selection Sort Pseudocode

FOR i = 0 TO n - 1

    minIndex = i

    FOR j = i + 1 TO n - 1

        IF array[j] < array[minIndex]

            minIndex = j

        END IF

    END FOR

    SWAP array[i] and array[minIndex]

END FOR

Selection Sort in Python

def selection_sort(numbers):

    n = len(numbers)

    for i in range(n):

        min_index = i

        for j in range(i + 1, n):

            if numbers[j] < numbers[min_index]:
                min_index = j

        numbers[i], numbers[min_index] = (
            numbers[min_index],
            numbers[i]
        )

    return numbers

Selection Sort Complexity

Selection Sort always scans the remaining elements to find the minimum.

Therefore:

Best:    O(n²)
Average: O(n²)
Worst:   O(n²)

Space:

O(1)

One advantage is that it performs relatively few swaps compared with some simple sorting algorithms.

Part 3: Insertion Sort

Now we reach an algorithm that is much more interesting.

Insertion Sort

Insertion Sort works similarly to how many people naturally sort playing cards.

Imagine holding:

7

Then you receive:

3

You insert 3 before 7:

3 7

Then receive:

9

3 7 9

Then:

5

Insert it between 3 and 7:

3 5 7 9

That's the basic idea behind Insertion Sort.

Insertion Sort Example

Start:

[5, 3, 8, 4, 2]

Treat the first element as sorted:

[5] [3, 8, 4, 2]

Take 3.

Compare with 5.

Since:

3 < 5

insert it before 5:

[3, 5] [8, 4, 2]

Take 8.

It's already larger:

[3, 5, 8] [4, 2]

Take 4.

Move 8:

[3, 5, _, 8, 2]

Move 5:

[3, _, 5, 8, 2]

Insert 4:

[3, 4, 5, 8, 2]

Finally insert 2:

[2, 3, 4, 5, 8]

Sorted.

Insertion Sort Pseudocode

FOR i = 1 TO n - 1

    key = array[i]

    j = i - 1

    WHILE j >= 0 AND array[j] > key

        array[j + 1] = array[j]

        j = j - 1

    END WHILE

    array[j + 1] = key

END FOR

Insertion Sort in Python

def insertion_sort(numbers):

    for i in range(1, len(numbers)):

        key = numbers[i]

        j = i - 1

        while j >= 0 and numbers[j] > key:

            numbers[j + 1] = numbers[j]

            j -= 1

        numbers[j + 1] = key

    return numbers

Insertion Sort Complexity

Worst case:

O(n²)

Average:

O(n²)

But the best case is:

O(n)

when the array is already sorted or nearly sorted.

That's an important characteristic.

Why Insertion Sort Is Still Useful

You might ask:

"If Merge Sort and Quick Sort are faster, why learn Insertion Sort?"

Because Insertion Sort performs well when:

• Data is small.
• Data is nearly sorted.
• You receive data incrementally.
• You need a simple implementation.
• You want an in-place algorithm.

Some sophisticated sorting implementations actually use insertion-style sorting for small partitions because its low overhead can make it efficient on tiny datasets.

Stability in Sorting

Now we're entering an important concept.

Suppose we have students:

Aman  90
Rahul 90
Priya 80

Suppose we sort by marks.

A stable sorting algorithm preserves the original relative order of elements with equal keys.

So:

Aman  90
Rahul 90

remain in that order.

Stability can matter when sorting records by multiple criteria.

For example:

First sort by:

Name

Then sort by:

Marks

A stable sort can preserve the earlier ordering among students with equal marks.

In-Place Sorting

An in-place sorting algorithm uses very little additional memory.

For example:

Input array
     ↓
Modify same array
     ↓
Sorted array

Bubble Sort, Selection Sort, and typical Insertion Sort implementations are:

O(1)

in auxiliary space.

Merge Sort generally requires additional memory for its merging process.

Comparison-Based Sorting

Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, and Quick Sort are based on comparing elements.

They repeatedly ask questions such as:

Is A < B?

or:

Is A > B?

These are called comparison-based sorting algorithms.

There are also sorting algorithms that exploit properties of the values themselves.

We'll encounter those later.

Why Simple Sorts Are Usually O(n²)

Consider what happens when you repeatedly compare many elements against each other.

For example:

n × n

produces:

n²

That's why many elementary sorting algorithms have:

O(n²)

complexity.

This is fine for small inputs.

But it becomes increasingly expensive as n grows.

Comparing the Three Basic Sorts

The exact stability/optimization behavior depends on implementation, but these are the common textbook characteristics.

Why Do We Need Faster Sorting?

Imagine:

n = 10

An O(n²) algorithm performs around:

100

units of pairwise work.

Not terrible.

Now:

n = 1,000

approximately:

1,000,000

units.

Now:

n = 1,000,000

approximately:

1,000,000,000,000

That is:

1 trillion

scale.

We need better strategies.

The Big Idea: Divide and Conquer

One of the most important techniques in algorithms is:

Divide and Conquer

Instead of trying to solve a huge problem directly:

Huge Problem

we divide it:

        Problem
        /     \
     Part     Part
     / \       / \
    ...       ...

Solve the smaller problems.

Then combine their results.

This idea leads us directly to one of the most important sorting algorithms:

Merge Sort

Merge Sort Preview

Suppose:

[8, 3, 5, 4, 7, 6, 1, 2]

Split:

[8, 3, 5, 4] [7, 6, 1, 2]

Split again:

[8, 3] [5, 4] [7, 6] [1, 2]

Again:

[8] [3] [5] [4] [7] [6] [1] [2]

Now merge sorted pieces:

[3, 8]
[4, 5]
[6, 7]
[1, 2]

Then:

[3, 4, 5, 8]
[1, 2, 6, 7]

Finally:

[1, 2, 3, 4, 5, 6, 7, 8]

That's Merge Sort.

And its complexity is:

O(n log n)

We'll explore it in detail in the next article.

Understanding the Complexity Jump

We've seen:

Bubble Sort       O(n²)
Selection Sort    O(n²)
Insertion Sort    O(n²)

Then:

Merge Sort        O(n log n)

That difference is significant.

For a large dataset, moving from:

n²

to:

n log n

can dramatically improve scalability.

A Useful Mental Model

Think of sorting algorithms as different strategies for organizing chaos.

Bubble Sort

Compare neighbors
→ swap
→ repeat

Selection Sort

Find minimum
→ place it
→ repeat

Insertion Sort

Take next item
→ insert into sorted portion
→ repeat

Merge Sort

Divide
→ solve smaller pieces
→ merge

Quick Sort

Choose pivot
→ partition
→ recursively solve

Each algorithm represents a different way of thinking.

Common Interview Questions

Which sorting algorithm is easiest to understand?

Usually:

Bubble Sort

It has a very simple idea and is excellent for learning algorithm fundamentals.

Which simple sorting algorithm works well on nearly sorted data?

Insertion Sort

Its best-case behavior can be:

O(n)

when the input is already sorted.

Which basic sorting algorithms are in-place?

Typical implementations of:

• Bubble Sort
• Selection Sort
• Insertion Sort

use:

O(1)

auxiliary space.

Why is Merge Sort faster asymptotically?

Merge Sort divides the input into smaller pieces and efficiently merges them.

Its overall complexity is:

O(n log n)

instead of the quadratic behavior of the elementary sorts.

A Small Challenge

Try sorting this manually using Insertion Sort:

[7, 4, 9, 2, 6]

Start:

[7]

Insert 4:

[4, 7]

Insert 9:

[4, 7, 9]

Now insert:

2

Then:

6

Final result:

[2, 4, 6, 7, 9]

Don't just memorize the result.

Practice the movement of elements.

That's what helps you understand the algorithm.

Algorithmic Thinking: The Bigger Lesson

At this stage, notice how our algorithms are evolving.

We started with:

Linear Search
O(n)

Then:

Binary Search
O(log n)

Now we're looking at:

Sorting

Sorting is important because it can transform the structure of the problem.

Once data is organized, we can often perform other operations much more efficiently.

This is a recurring pattern in computer science:

Spend computational effort organizing information so future operations become cheaper.

Final Takeaways

Today we introduced the fundamental sorting algorithms.

Bubble Sort

Repeatedly compares neighboring elements.

O(n²)

Selection Sort

Repeatedly selects the smallest remaining element.

O(n²)

Insertion Sort

Builds a sorted portion one element at a time.

Best: O(n)
Worst: O(n²)

And we introduced the concepts of:

• Stable sorting
• In-place sorting
• Comparison-based sorting
• Divide and conquer
• Preprocessing
• Algorithm trade-offs

The most important thing isn't memorizing code.

It's understanding the strategy behind each algorithm.

Different problems require different ways of thinking.