Sorting Algorithms

Sorting means arranging elements in a particular order.

For example:

Before:
[5, 2, 8, 1, 3]

After:
[1, 2, 3, 5, 8]



There are many sorting algorithms. Here we will look at three basic ones:

Bubble Sort
Selection Sort
Insertion Sort

The important thing is to understand how each algorithm works instead of just memorizing the code.

1. Bubble Sort
What is Bubble Sort?

Bubble Sort compares two elements next to each other.

If they are in the wrong order, they are swapped.

For example:

[5, 3, 8, 4]

Compare 5 and 3

5 > 3

Swap them:

[3, 5, 8, 4]


Then we compare the next pair:

[3, 5, 8, 4]

Compare 5 and 8

5 < 8

No swap.


Then:

[3, 5, 8, 4]

Compare 8 and 4

8 > 4

Swap:

[3, 5, 4, 8]


After one complete pass, the largest element has moved to the end.

[3, 5, 4, 8]
         ^
         largest


This is where the name Bubble Sort comes from. Large elements keep moving toward the end of the array.

How Bubble Sort works

Suppose we have:

[5, 1, 4, 2, 8]

First pass

Compare 5 and 1:

[1, 5, 4, 2, 8]


Compare 5 and 4:

[1, 4, 5, 2, 8]


Compare 5 and 2:

[1, 4, 2, 5, 8]


Compare 5 and 8:

[1, 4, 2, 5, 8]


Now 8 is in its correct position.

Second pass

We don't need to check 8 again.

[1, 4, 2, 5 | 8]


Compare 1 and 4:

[1, 4, 2, 5 | 8]


Compare 4 and 2:

[1, 2, 4, 5 | 8]


Compare 4 and 5:

[1, 2, 4, 5 | 8]


Now both 5 and 8 are in the correct positions.

Continue until the whole array is sorted.

Final result:

[1, 2, 4, 5, 8]

Bubble Sort code
function bubbleSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    let swapped = false;

    for (let j = 0; j < arr.length - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        swapped = true;
      }
    }

    if (!swapped) {
      break;
    }
  }

  return arr;
}

Why do we use swapped?

Consider an already sorted array:

[1, 2, 3, 4, 5]


There is nothing to swap.

Without the swapped check, Bubble Sort would continue making unnecessary passes.

With the check:

No swap happened
       |
       v
Array is already sorted
       |
       v
Stop


This improves the best case from O(n²) to O(n).

Time and space complexity
Case	Complexity
Best case	O(n)
Average case	O(n²)
Worst case	O(n²)
Space	O(1)

The O(n) best case assumes the early-stop optimization is used.

When should you use Bubble Sort?

Bubble Sort is mainly useful for learning.

It is easy to understand and is a good example for learning:

Comparisons
Swapping
Nested loops
Time complexity

It is generally not a good choice for large datasets.

Remember
Bubble Sort

Compare neighbors
       ↓
Swap if they are in the wrong order
       ↓
Largest element moves to the end
       ↓
Repeat

2. Selection Sort
What is Selection Sort?

Selection Sort works by finding the smallest element and putting it in the correct position.

For example:

[5, 3, 8, 1, 4]


First, find the smallest element.

Smallest = 1


Put 1 at the beginning:

[1, 3, 8, 5, 4]


Now we don't need to worry about 1.

Look at the remaining elements:

[1 | 3, 8, 5, 4]


Find the smallest:

3


It is already in the correct position.

Then look at:

[1, 3 | 8, 5, 4]


The smallest is 4.

Put it in the correct position:

[1, 3, 4, 5, 8]


The array is sorted.

The main idea

Selection Sort divides the array into two parts:

Sorted | Unsorted


At the beginning:

[] | [5, 3, 8, 1, 4]


After the first pass:

[1] | [3, 8, 5, 4]


After the second pass:

[1, 3] | [8, 5, 4]


After the third pass:

[1, 3, 4] | [8, 5]


Eventually:

[1, 3, 4, 5, 8] | []

Step-by-step example

Let's sort:

[64, 25, 12, 22, 11]

First pass

Start at index 0.

Find the smallest element:

64, 25, 12, 22, 11
                  ^
                smallest


Smallest is 11.

Swap 64 and 11:

[11, 25, 12, 22, 64]


11 is now fixed.

Second pass

Ignore the first element.

[11 | 25, 12, 22, 64]


Smallest in the remaining part is 12.

Swap:

[11, 12, 25, 22, 64]

Third pass
[11, 12 | 25, 22, 64]


Smallest is 22.

Swap:

[11, 12, 22, 25, 64]

Fourth pass
[11, 12, 22 | 25, 64]


Smallest is already 25.

The array is sorted:

[11, 12, 22, 25, 64]

Selection Sort code
function selectionSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let minIndex = i;

    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }

    [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
  }

  return arr;
}

Why do we use minIndex?

We don't immediately swap every time we find a smaller value.

Instead, we remember where the smallest value is.

Example:

[7, 4, 5, 2, 6]


Start:

minIndex = 0
minimum = 7


Check 4:

4 < 7

minimum = 4


Check 5:

5 < 4?

No.


Check 2:

2 < 4

minimum = 2


Check 6:

6 < 2?

No.


At the end:

minimum = 2


Now swap it with the first element.

[2, 4, 5, 7, 6]


This is the main idea behind Selection Sort:

Find minimum
      ↓
Remember its position
      ↓
Swap once

Time and space complexity
Case	Complexity
Best case	O(n²)
Average case	O(n²)
Worst case	O(n²)
Space	O(1)

Even if the array is already sorted, Selection Sort still needs to search the remaining elements to find the minimum.

For example:

[1, 2, 3, 4, 5]


It still checks the remaining elements on every pass.

One useful property

Selection Sort does relatively few swaps.

It performs at most around n - 1 swaps.

So while it makes many comparisons, it doesn't constantly swap elements.

When should you use Selection Sort?

Selection Sort is mainly useful for:

Learning sorting
Understanding the minimum-selection pattern
Understanding how to separate sorted and unsorted parts
Situations where the number of swaps matters

For large datasets, it is usually not the best choice.

Remember
Selection Sort

Find the smallest element
        ↓
Put it at the current position
        ↓
Move to the next position
        ↓
Repeat

3. Insertion Sort
What is Insertion Sort?

Insertion Sort works in a similar way to arranging playing cards in your hand.

Suppose you have:

[2, 5, 8]


Now you get the number:

4


Where should 4 go?

Between 2 and 5:

[2, 4, 5, 8]


That is the basic idea of Insertion Sort.

You take one element at a time and insert it into the correct position in the already sorted part.

The main idea

Insertion Sort also divides the array into two parts:

Sorted | Unsorted


For example:

[2, 4, 5 | 8, 1, 7]


The left side is already sorted.

Take 8:

[2, 4, 5 | 8]


Since 8 is greater than 5, it can stay where it is.

Now take 1.

We need to move larger elements to the right:

[2, 4, 5, 8 | 1]


Move 8:

[2, 4, 5, 8, 8]


Move 5:

[2, 4, 5, 5, 8]


Move 4:

[2, 4, 4, 5, 8]


Move 2:

[2, 2, 4, 5, 8]


Now insert 1:

[1, 2, 4, 5, 8]

Step-by-step example

Let's sort:

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

Start

The first element is considered sorted:

[5 | 2, 4, 6, 1, 3]

Insert 2

Compare 2 with 5.

2 < 5


Move 5 to the right:

[5, 5, 4, 6, 1, 3]


Insert 2:

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


Now:

[2, 5 | 4, 6, 1, 3]

Insert 4

Compare 4 with 5.

4 < 5


Move 5:

[2, 5, 5, 6, 1, 3]


Now compare 4 with 2.

4 > 2


Stop and insert 4:

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

Insert 6

6 is already greater than 5.

So:

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

Insert 1

Everything before 1 is greater than it.

Move:

6 → right
5 → right
4 → right
2 → right


Then insert 1:

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

Insert 3

Compare 3 with 6:

6 > 3


Move 6.

Compare 3 with 5:

5 > 3


Move 5.

Compare 3 with 4:

4 > 3


Move 4.

Compare 3 with 2:

2 < 3


Stop.

Insert 3:

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


Sorted.

Insertion Sort code
function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    const key = arr[i];
    let j = i - 1;

    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }

    arr[j + 1] = key;
  }

  return arr;
}

What does key mean?

key is the element we are currently trying to place.

For example:

[2, 4, 7 | 5]


Here:

key = 5


We want to find the correct position for 5.

We compare it with elements on the left and shift larger elements.

Eventually:

[2, 4, 5, 7]

Why is Insertion Sort good for nearly sorted arrays?

Consider:

[1, 2, 3, 5, 4]


Only 4 is out of place.

Insertion Sort doesn't need to rearrange the entire array.

It simply moves 5 and inserts 4:

[1, 2, 3, 4, 5]


This is why Insertion Sort can be useful when the data is already mostly sorted.

Time and space complexity
Case	Complexity
Best case	O(n)
Average case	O(n²)
Worst case	O(n²)
Space	O(1)
Best case

Already sorted:

[1, 2, 3, 4, 5]


Very little shifting is needed.

Time:

O(n)

Worst case

Reverse sorted:

[5, 4, 3, 2, 1]


Almost every element needs to move.

Time:

O(n²)

When should you use Insertion Sort?

Insertion Sort is useful when:

The array is small.
The array is already mostly sorted.
You want a simple in-place sorting algorithm.
You are learning how insertion and shifting work.

Among these three basic algorithms, Insertion Sort is often the most useful in practice for small or nearly sorted data.

Remember
Insertion Sort

Take one element
       ↓
Compare it with the sorted part
       ↓
Move larger elements right
       ↓
Insert the element
       ↓
Repeat

Bubble Sort vs Selection Sort vs Insertion Sort
Feature	Bubble Sort	Selection Sort	Insertion Sort
Main idea	Compare neighbors	Find minimum	Insert into sorted part
Best case	O(n)	O(n²)	O(n)
Average case	O(n²)	O(n²)	O(n²)
Worst case	O(n²)	O(n²)	O(n²)
Space	O(1)	O(1)	O(1)
Stable	Yes	Usually no	Yes
In-place	Yes	Yes	Yes
Good for nearly sorted data	Not usually	No	Yes
How to Identify the Algorithm

When reading a question, look for these patterns.

If you see adjacent comparisons

Think:

Bubble Sort


Example:

arr[j] and arr[j + 1]


The algorithm is comparing neighbors.

If you see minimum selection

Think:

Selection Sort


Typical pattern:

minIndex = i

Find the smallest element
Swap it with arr[i]

If you see shifting and inserting

Think:

Insertion Sort


Typical pattern:

key = arr[i]

Move larger elements to the right

Insert key

Quick Revision
Bubble Sort
Compare adjacent elements
Swap when needed
Largest element moves to the end


Time:

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

Selection Sort
Find the minimum
Swap it with the current position
Repeat


Time:

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

Insertion Sort
Take one element
Find where it belongs
Shift larger elements
Insert it


Time:

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

Final Takeaway

The easiest way to remember these three algorithms is:

Bubble Sort
→ Compare neighbors

Selection Sort
→ Find the minimum

Insertion Sort
→ Insert into the sorted part


All three can sort an array, but they work differently.

For learning DSA, understanding these differences is more important than memorizing the code.

A useful way to think about them is:

Bubble:
"Are these two next to each other in the right order?"

Selection:
"What is the smallest element left?"

Insertion:
"Where should this element be inserted?"

Once these three ideas are clear, the implementation becomes much easier to remember.