Time to get spicy 🔥 with one of the most widely used and interview-famous sorting algorithms in existence:
Quick Sort — the fast-talking, divide-and-conquer bad boy of the algorithm world.

It’s like Merge Sort’s chaotic sibling who says,

“Nah bro, I don’t need extra arrays. I’ll just do it in-place and still beat everyone to the finish line.”

Let’s break it down — and implement it with arrays in Java.

---

⚡️ Quick Sort (Array Implementation in Java)

“Pick a pivot. Break things. Recursively clean up the mess.”
— Quick Sort, the drama king of sorts

---

🧠 What is Quick Sort?

Quick Sort is a Divide and Conquer algorithm that:

1. Picks a pivot element

2. Partitions the array so that:

   • Elements < pivot go left

   • Elements > pivot go right

3. Recursively sorts each partition

All done in-place, with no need for fancy helper arrays.

---

📊 Time & Space Complexity

---

🛠️ Java Array Implementation of Quick Sort

Here it is — clean, recursive, array-based Quick Sort:

java
CopyEdit
public class QuickSort {

    public void sort(int[] arr) {
        if (arr == null || arr.length < 2) return;
        quickSort(arr, 0, arr.length - 1);
    }

    private void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            // Partition the array and get pivot index
            int pivotIndex = partition(arr, low, high);

            // Recursively sort elements before and after partition
            quickSort(arr, low, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, high);
        }
    }

    // Lomuto partition scheme (pivot = last element)
    private int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = low - 1; // index of smaller element

        for (int j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                i++;
                // swap arr[i] and arr[j]
                swap(arr, i, j);
            }
        }

        // swap pivot to correct position
        swap(arr, i + 1, high);
        return i + 1;
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    // Demo
    public static void main(String[] args) {
        int[] arr = {10, 7, 8, 9, 1, 5};

        QuickSort sorter = new QuickSort();
        sorter.sort(arr);

        System.out.println("Sorted array:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

---

🔍 How It Works (Step-by-Step)

Let’s say we have:

java
CopyEdit
arr = [10, 7, 8, 9, 1, 5]

1. Pivot = 5 (last element)

2. Partition: move elements < 5 to the left

3. Swap pivot to its correct position

4. Recursively repeat on both sides

---

🔥 Why Quick Sort Is... Quick

• ✅ Works in-place (no extra memory like Merge Sort)

• ✅ Great for average-case performance

• ✅ Used in real-world systems (with tweaks)

• ✅ Often faster than Merge Sort in practice for in-memory sorting

---

⚠️ But Watch Out

• ❌ Worst case = O(n²), especially if:

  • Pivot is always the smallest/largest

  • Input is already sorted

• ✅ Fix: Use randomized pivot or median-of-three strategy

Example randomized pivot:

java
CopyEdit
int pivotIndex = low + new Random().nextInt(high - low + 1);
swap(arr, pivotIndex, high); // Then continue as normal

---

💡 Quick Sort vs Merge Sort

Quick Sort wins for speed and in-place magic, but Merge Sort is safer when stability matters or you're dealing with linked lists.

---

🧠 TL;DR (Too Long, Didn’t Pivot)

• Quick Sort is a recursive, in-place, divide-and-conquer algorithm

• Picks a pivot, partitions the array, and recurses on both sides

• Average time = O(n log n), worst = O(n²) (use randomized pivot to avoid this)

• In-place and memory efficient

• One of the most popular sorting algorithms for a reason

---

🎓 Final Thoughts From the Sorting Arena

If Merge Sort is the clean, recursive academic, Quick Sort is the street-smart algorithm that cuts through the mess with ruthless efficiency (and minimal RAM usage).

You’ll see Quick Sort everywhere:

• In coding interviews

• In real-world libraries

• In your own future projects

So learn it. Love it. Know when to use it (and when to not).
It’s the fast-talking, efficient legend your CS journey deserves.