🔢 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

1. Start from the beginning of the array.

2. Compare adjacent elements.

3. Swap if the left is greater than the right.

4. 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

1. Start from index 1.

2. Compare it to elements before it.

3. Shift larger elements to the right.

4. 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

1. Loop through the array to find the smallest.

2. Swap it with the first unsorted element.

3. 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

1. Divide the array into halves.

2. Recursively sort each half.

3. 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

1. Choose a pivot.

2. Partition the array around it.

3. 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.