🔢 Java Sorting Algorithms — Step-by-Step with Iterations

Sorting is a fundamental concept in programming and data structures.
Below are the five main sorting algorithms, explained in simple terms with visual examples, loop-by-loop walkthroughs, and complete Java programs.

🧮 1️⃣ Bubble Sort — Iteration by Iteration

💡 Concept

Bubble Sort repeatedly compares adjacent elements and swaps them if they’re in the wrong order.
With each pass, the largest element “bubbles” to the end of the array.

⚙️ How It Works

Start from the beginning of the array.
Compare adjacent elements.
Swap if the left is greater than the right.
Repeat until no more swaps are needed.

🧩 Example: `[5, 4, 1, 3]`

Initial Array:
[5, 4, 1, 3]

Pass 1

Comparison	Operation	Result
Compare 5 & 4	Swap	[4, 5, 1, 3]
Compare 5 & 1	Swap	[4, 1, 5, 3]
Compare 5 & 3	Swap	[4, 1, 3, 5]
✅ Largest element (5) “bubbled” to end.

Pass 2

Comparison	Operation	Result
Compare 4 & 1	Swap	[1, 4, 3, 5]
Compare 4 & 3	Swap	[1, 3, 4, 5]
✅ Second largest (4) in place.

Pass 3

Comparison	Operation	Result
Compare 1 & 3	No swap	[1, 3, 4, 5]
✅ Sorted.

💻 Java Code


package com.vi.sort;

import java.util.Arrays;

public class BubbleSort {
    public static void main(String[] args) {
        int[] a = {5, 4, 1, 3};
        System.out.println("Before Sorting: " + Arrays.toString(a));
        doBubbleSort(a);
        System.out.println("After Sorting: " + Arrays.toString(a));
    }

    public static void doBubbleSort(int[] a) {
        boolean sorted = false;
        int iteration = 1;
        while (!sorted) {
            sorted = true;
            System.out.println("Iteration " + iteration++ + ": " + Arrays.toString(a));
            for (int i = 0; i < a.length - 1; i++) {
                if (a[i] > a[i + 1]) {
                    int temp = a[i];
                    a[i] = a[i + 1];
                    a[i + 1] = temp;
                    sorted = false;
                }
            }
        }
    }
}

🧾 Output


Before Sorting: [5, 4, 1, 3]
Iteration 1: [5, 4, 1, 3]
Iteration 2: [4, 1, 3, 5]
Iteration 3: [1, 3, 4, 5]
After Sorting: [1, 3, 4, 5]

🧠 Key Points

Each pass “bubbles” the largest remaining element to the end.
Works well for small datasets.
Time: O(n²), Space: O(1), Stable: ✅ Yes

🧩 2️⃣ Insertion Sort — Iteration by Iteration

💡 Concept

Insertion Sort builds a sorted portion of the array one element at a time.
Each element is compared backward and inserted into its correct position.

⚙️ How It Works

Start from index 1.
Compare it to elements before it.
Shift larger elements to the right.
Insert current element into correct place.

🧩 Example: `[5, 4, 1, 3]`

Iteration 1 (key=4):
4 < 5 → shift → [5,5,1,3]
Insert 4 → [4,5,1,3]

Iteration 2 (key=1):
1 < 5 → shift → [4,5,5,3]
1 < 4 → shift → [4,4,5,3]
Insert 1 → [1,4,5,3]

Iteration 3 (key=3):
3 < 5 → shift → [1,4,5,5]
3 < 4 → shift → [1,4,4,5]
Insert 3 → [1,3,4,5] ✅

💻 Java Code


package com.vi.sort;

import java.util.Arrays;

public class InsertionSort {
    public static void main(String[] args) {
        int[] a = {5, 4, 1, 3};
        System.out.println("Before Sorting: " + Arrays.toString(a));
        doInsertionSort(a);
        System.out.println("After Sorting: " + Arrays.toString(a));
    }

    public static void doInsertionSort(int[] a) {
        for (int i = 1; i < a.length; i++) {
            int key = a[i];
            int j = i - 1;
            while (j >= 0 && a[j] > key) {
                a[j + 1] = a[j];
                j--;
            }
            a[j + 1] = key;
            System.out.println("Iteration " + i + ": " + Arrays.toString(a));
        }
    }
}

🧾 Output


Iteration 1: [4, 5, 1, 3]
Iteration 2: [1, 4, 5, 3]
Iteration 3: [1, 3, 4, 5]

🧠 Key Points

Works best on nearly sorted arrays.
Time: O(n²), Space: O(1), Stable: ✅ Yes
Ideal for real-time insertion problems.

🧩 3️⃣ Selection Sort — Iteration by Iteration

💡 Concept

Selection Sort repeatedly finds the smallest element from the unsorted part and places it at the start.

⚙️ How It Works

Loop through the array to find the smallest.
Swap it with the first unsorted element.
Move the sorted boundary forward.

🧩 Example: `[5, 4, 1, 3]`

Pass	Smallest	Swap	Result
1	1	1 ↔ 5	[1, 4, 5, 3]
2	3	3 ↔ 4	[1, 3, 5, 4]
3	4	4 ↔ 5	[1, 3, 4, 5]
✅ Sorted `[1, 3, 4, 5]`

💻 Java Code


package com.vi.sort;

import java.util.Arrays;

public class SelectionSort {
    public static void main(String[] args) {
        int[] a = {5, 4, 1, 3};
        System.out.println("Before Sorting: " + Arrays.toString(a));
        doSelectionSort(a);
        System.out.println("After Sorting: " + Arrays.toString(a));
    }

    public static void doSelectionSort(int[] a) {
        for (int i = 0; i < a.length - 1; i++) {
            int min = i;
            for (int j = i + 1; j < a.length; j++) {
                if (a[j] < a[min]) {
                    min = j;
                }
            }
            int temp = a[min];
            a[min] = a[i];
            a[i] = temp;
            System.out.println("Iteration " + (i + 1) + ": " + Arrays.toString(a));
        }
    }
}

🧾 Output


Iteration 1: [1, 4, 5, 3]
Iteration 2: [1, 3, 5, 4]
Iteration 3: [1, 3, 4, 5]

🧠 Key Points

Simple but slow.
Time: O(n²), Space: O(1), Stable: ❌ No.
Best when minimizing swaps.

🧩 4️⃣ Merge Sort — Iteration by Iteration

💡 Concept

Merge Sort follows divide and conquer — splitting the array, sorting halves, and merging them.

⚙️ How It Works

Divide the array into halves.
Recursively sort each half.
Merge the two sorted halves.

🧩 Example: `[5, 4, 1, 3]`


Divide → [5,4] [1,3]
Sort → [4,5] [1,3]
Merge → [1,3,4,5]

Merge process:
Left [4,5], Right [1,3]
1 < 4 → pick 1
3 < 4 → pick 3
Append remaining → [1,3,4,5]

💻 Java Code


package com.vi.sort;

import java.util.Arrays;

public class MergeSort {
    public static void main(String[] args) {
        int[] a = {5, 4, 1, 3};
        System.out.println("Before Sorting: " + Arrays.toString(a));
        mergeSort(a, 0, a.length - 1);
        System.out.println("After Sorting: " + Arrays.toString(a));
    }

    public static void mergeSort(int[] a, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            mergeSort(a, left, mid);
            mergeSort(a, mid + 1, right);
            merge(a, left, mid, right);
        }
    }

    public static void merge(int[] a, int left, int mid, int right) {
        int n1 = mid - left + 1, n2 = right - mid;
        int[] L = new int[n1];
        int[] R = new int[n2];
        for (int i = 0; i < n1; i++) L[i] = a[left + i];
        for (int j = 0; j < n2; j++) R[j] = a[mid + 1 + j];

        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) a[k++] = L[i++];
            else a[k++] = R[j++];
        }
        while (i < n1) a[k++] = L[i++];
        while (j < n2) a[k++] = R[j++];
        System.out.println("Merging step: " + Arrays.toString(a));
    }
}

🧾 Output


Before Sorting: [5, 4, 1, 3]
Merging step: [4, 5, 1, 3]
Merging step: [4, 5, 1, 3]
Merging step: [1, 3, 4, 5]
After Sorting: [1, 3, 4, 5]

🧠 Key Points

Time: O(n log n), Space: O(n)
Stable: ✅ Yes
Great for large datasets or linked lists.

🧩 5️⃣ Quick Sort — Iteration by Iteration

💡 Concept

Quick Sort also uses divide and conquer — but partitions around a pivot element.

⚙️ How It Works

Choose a pivot.
Partition the array around it.
Recursively apply on left and right sides.

🧩 Example: `[5, 4, 1, 3]`

Step 1: Pivot = 3
→ Partition → [1, 3, 5, 4]
Step 2: Left [1] sorted, right [5,4] → Pivot = 4
→ Swap → [1, 3, 4, 5] ✅

💻 Java Code


package com.vi.sort;

import java.util.Arrays;

public class QuickSort {
    public static void main(String[] args) {
        int[] a = {5, 4, 1, 3};
        System.out.println("Before Sorting: " + Arrays.toString(a));
        quickSort(a, 0, a.length - 1);
        System.out.println("After Sorting: " + Arrays.toString(a));
    }

    public static void quickSort(int[] a, int low, int high) {
        if (low < high) {
            int pi = partition(a, low, high);
            System.out.println("After partition (pivot index " + pi + "): " + Arrays.toString(a));
            quickSort(a, low, pi - 1);
            quickSort(a, pi + 1, high);
        }
    }

    public static int partition(int[] a, int low, int high) {
        int pivot = a[high];
        int i = low - 1;
        for (int j = low; j < high; j++) {
            if (a[j] < pivot) {
                i++;
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }
        int temp = a[i + 1];
        a[i + 1] = a[high];
        a[high] = temp;
        return i + 1;
    }
}

🧾 Output


Before Sorting: [5, 4, 1, 3]
After partition (pivot index 1): [1, 3, 5, 4]
After partition (pivot index 3): [1, 3, 4, 5]
After Sorting: [1, 3, 4, 5]

🧠 Key Points

Average: O(n log n), Worst: O(n²)
Space: O(log n)
Stable: ❌ No
Used internally in Arrays.sort() for primitives.

📊 Sorting Algorithm Summary Table

Algorithm	Time Complexity	Space	Stable	Best Use
Bubble Sort	O(n²)	O(1)	✅	Educational, small datasets
Insertion Sort	O(n²)	O(1)	✅	Small or nearly sorted data
Selection Sort	O(n²)	O(1)	❌	Minimal swaps
Merge Sort	O(n log n)	O(n)	✅	Large or linked data
Quick Sort	O(n log n) avg	O(log n)	❌	Fast general-purpose sorting

🧭 Final Thoughts

🧮 Bubble Sort → Great for beginners.
✏️ Insertion Sort → Efficient for small, sorted data.
🧲 Selection Sort → Minimal swaps, easy to implement.
⚙️ Merge Sort → Predictable performance, always O(n log n).
⚡ Quick Sort → Industry favorite; excellent average speed.