Sorting Algorithms

🎯 Sorting Algorithms: Teaching Your Cards to Line Up!

Imagine you have a messy pile of playing cards. You want them in order from smallest to biggest. How do you do it? That’s exactly what sorting algorithms solve!

Think of sorting like organizing a line of kids by height for a class photo. Different teachers use different methods—some are fast, some are careful, and some work better with certain groups of kids!

🃏 Insertion Sort: The Card Player’s Method

The Story

You’re playing cards. Each time you pick up a new card, you slide it into the right spot in your hand. That’s Insertion Sort!

How It Works

1. Start with one card (it’s already “sorted”)
2. Pick the next card
3. Slide it left until it finds its home
4. Repeat until all cards are in place

Simple Example

Cards: [5, 2, 8, 1]

Step 1: [5] ← Start with 5
Step 2: [2, 5] ← Insert 2 before 5
Step 3: [2, 5, 8] ← 8 stays at end
Step 4: [1, 2, 5, 8] ← Insert 1 at start

Done! 🎉

Java Code

void insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

When to Use It?

✅ Small lists (under 50 items) ✅ Almost-sorted data ✅ When simplicity matters

Speed: O(n²) — Slow for big lists, but great for tiny ones!

🧬 Divide and Conquer Fundamentals

The Big Idea

Imagine cleaning your entire messy room. Overwhelming, right?

But what if you:

1. Divide — Split the room into corners
2. Conquer — Clean each corner separately
3. Combine — Put everything back together

That’s Divide and Conquer! Break big problems into tiny pieces.

graph TD
    A["Big Problem"] --> B["Small Problem 1"]
    A --> C["Small Problem 2"]
    B --> D["Solution 1"]
    C --> E["Solution 2"]
    D --> F["Combined Solution"]
    E --> F

Why Does This Work?

Small problems are easy to solve. Solving 10 tiny puzzles is faster than one giant puzzle!

🔀 Merge Sort: The Team Splitter

The Story

You’re a teacher sorting 100 test papers by score. Instead of doing it alone, you:

1. Split papers into two piles
2. Give each pile to a helper
3. Each helper splits their pile again
4. Keep splitting until each person has 1 paper
5. Now merge them back in order!

How It Works

graph TD
    A["[38, 27, 43, 3]"] --> B["[38, 27]"]
    A --> C["[43, 3]"]
    B --> D["[38]"]
    B --> E["[27]"]
    C --> F["[43]"]
    C --> G["[3]"]
    D --> H["[27, 38]"]
    E --> H
    F --> I["[3, 43]"]
    G --> I
    H --> J["[3, 27, 38, 43]"]
    I --> J

Simple Example

Start: [38, 27, 43, 3]

Split: [38, 27] and [43, 3]
Split: [38] [27] [43] [3]

Merge: [27, 38] and [3, 43]
Merge: [3, 27, 38, 43]

Done! 🎉

Java Code

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

void merge(int[] arr, int l, int m, int r) {
    int[] L = Arrays.copyOfRange(arr, l, m+1);
    int[] R = Arrays.copyOfRange(arr, m+1, r+1);
    int i = 0, j = 0, k = l;
    while (i < L.length && j < R.length) {
        arr[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];
    }
    while (i < L.length) arr[k++] = L[i++];
    while (j < R.length) arr[k++] = R[j++];
}

The Magic

Speed: O(n log n) — Super fast even for millions of items!

✅ Always the same speed (predictable) ✅ Great for huge datasets ❌ Uses extra memory for merging

⚡ Quick Sort: The Pivot Master

The Story

Imagine you’re organizing books by height. You pick ONE book as the “pivot.” All shorter books go LEFT. All taller books go RIGHT. Then repeat for each side!

How It Works

1. Pick a pivot (usually last element)
2. Put smaller items LEFT of pivot
3. Put larger items RIGHT of pivot
4. Pivot is now in its final spot!
5. Repeat for left and right sides

Simple Example

Start: [10, 7, 8, 9, 1, 5]
Pivot: 5

Partition:
  Left of 5: [1]
  Right of 5: [10, 7, 8, 9]

Result: [1, 5, 10, 7, 8, 9]
        ↑ pivot is HOME!

Keep going with each side...
Final: [1, 5, 7, 8, 9, 10]

Java Code

void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int partition(int[] arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr, i, j);
        }
    }
    swap(arr, i + 1, high);
    return i + 1;
}

The Truth About Quick Sort

Average Speed: O(n log n) — Usually the fastest! Worst Case: O(n²) — When pivot is always smallest/largest

✅ Very fast in practice ✅ Sorts “in place” (no extra memory) ❌ Can be slow with bad pivot choices

🔢 Counting Sort: The Bucket Counter

The Story

You have 100 dice showing numbers 1-6. Instead of comparing dice, just COUNT how many of each number you have!

How It Works

1. Count occurrences of each value
2. Calculate positions from counts
3. Place items in their positions

Simple Example

Input: [4, 2, 2, 8, 3, 3, 1]

Count:
  1 → 1 time
  2 → 2 times
  3 → 2 times
  4 → 1 time
  8 → 1 time

Output: [1, 2, 2, 3, 3, 4, 8]

Java Code

void countingSort(int[] arr, int max) {
    int[] count = new int[max + 1];
    int[] output = new int[arr.length];

    for (int num : arr) count[num]++;
    for (int i = 1; i <= max; i++) {
        count[i] += count[i - 1];
    }
    for (int i = arr.length - 1; i >= 0; i--) {
        output[count[arr[i]] - 1] = arr[i];
        count[arr[i]]--;
    }
    System.arraycopy(output, 0, arr, 0, arr.length);
}

The Superpower

Speed: O(n + k) where k is the range

✅ Faster than comparison sorts! ✅ Perfect for integers in a known range ❌ Needs extra memory ❌ Only works for integers

🎭 Sorting Stability: Keeping the Order

What Is Stability?

When two items have the same value, a stable sort keeps them in their original order.

Why Does It Matter?

Imagine sorting students by grade:

Before: [Anna-B, Bob-A, Carol-B, Dan-A]

Stable Sort by grade:
[Bob-A, Dan-A, Anna-B, Carol-B]
 ↑ Bob was before Dan, still is!

Unstable Sort might give:
[Dan-A, Bob-A, Carol-B, Anna-B]
 ↑ Order changed!

Which Sorts Are Stable?

Java Tip

// Java's Arrays.sort() for objects is STABLE
// It uses Merge Sort internally!
Arrays.sort(students,
    Comparator.comparing(s -> s.grade));

🎛️ Custom Comparators: Sort Your Way!

The Problem

What if you want to sort:

• Students by name?
• Products by price?
• Cards by suit then rank?

You need a Custom Comparator!

The Solution

// Sort by name (alphabetically)
Arrays.sort(students, (a, b) ->
    a.name.compareTo(b.name));

// Sort by age (youngest first)
Arrays.sort(students, (a, b) ->
    a.age - b.age);

// Sort by grade (highest first)
Arrays.sort(students, (a, b) ->
    b.grade - a.grade);

Multi-Level Sorting

// Sort by grade, then by name
Arrays.sort(students,
    Comparator.comparing(Student::getGrade)
              .thenComparing(Student::getName));

Real Example

class Student {
    String name;
    int age;
    char grade;
}

// Sort: First by grade (A-F),
// then by age (youngest first)
Arrays.sort(students, (a, b) -> {
    if (a.grade != b.grade) {
        return a.grade - b.grade;
    }
    return a.age - b.age;
});

🎯 Quick Select: Find the Kth Treasure

The Story

You don’t need to sort everything! You just want to find the 3rd smallest item. Quick Select finds it without sorting the whole list!

How It Works

It’s like Quick Sort, but smarter:

1. Pick a pivot and partition
2. If pivot is at position k—done!
3. If k is left of pivot—search left only
4. If k is right of pivot—search right only

Simple Example

Find 2nd smallest in [7, 10, 4, 3, 20, 15]

Partition around 15:
[7, 10, 4, 3] [15] [20]

2nd smallest is in left part!
Partition [7, 10, 4, 3] around 3:
[] [3] [7, 10, 4]

2nd smallest is in right part!
Partition [7, 10, 4] around 4:
[] [4] [7, 10]

Position of 4 = index 1 (2nd smallest)
Answer: 4 🎉

Java Code

int quickSelect(int[] arr, int low,
                int high, int k) {
    if (low == high) return arr[low];

    int pi = partition(arr, low, high);

    if (k == pi) return arr[pi];
    else if (k < pi)
        return quickSelect(arr, low, pi-1, k);
    else
        return quickSelect(arr, pi+1, high, k);
}

// Find kth smallest (0-indexed)
int kthSmallest = quickSelect(arr, 0,
                    arr.length - 1, k - 1);

The Magic

Average Speed: O(n) — Much faster than sorting! Use Case: Finding median, top-k elements

🏆 Algorithm Comparison Chart

🧠 Quick Decision Guide

graph TD
    A["Need to Sort?"] --> B{How many items?}
    B -->|Under 50| C["Insertion Sort"]
    B -->|50-10000| D{Need stable?}
    B -->|Over 10000| E{Data type?}
    D -->|Yes| F["Merge Sort"]
    D -->|No| G["Quick Sort"]
    E -->|Integers in range| H["Counting Sort"]
    E -->|Any type| F

🎓 Key Takeaways

1. Insertion Sort — Simple, great for small/nearly-sorted data
2. Merge Sort — Reliable O(n log n), stable, uses extra memory
3. Quick Sort — Usually fastest, but can be O(n²) with bad pivots
4. Counting Sort — Lightning fast for integers in a small range
5. Stability — Keeps equal elements in original order
6. Custom Comparators — Sort by any criteria you want
7. Quick Select — Find kth element without full sorting
8. Divide & Conquer — Split, solve, combine!

You’ve got this! 🚀 Now go sort some data!