1. The Hook (The "Byte-Sized" Intro)
In a Nutshell: Sorting arranges elements in order. Basic algorithms (Bubble, Selection, Insertion) are O(N²). Efficient algorithms (Quick, Merge) are O(N log N). Use Arrays.sort() for production!
When Amazon sorts products by price: Arrays.sort(products, Comparator.comparing(p -> p.price)). Fast, reliable, built-in!
2. Conceptual Clarity
Sorting Algorithms Comparison
| Algorithm | Time (Avg) | Time (Worst) | Space | Stable? |
|---|---|---|---|---|
| Bubble | O(N²) | O(N²) | O(1) | ✅ |
| Selection | O(N²) | O(N²) | O(1) | ❌ |
| Insertion | O(N²) | O(N²) | O(1) | ✅ |
| Quick | O(N log N) | O(N²) | O(log N) | ❌ |
| Merge | O(N log N) | O(N log N) | O(N) | ✅ |
| Arrays.sort | O(N log N) | O(N log N) | Varies | ✅* |
3. Interactive & Applied Code
import java.util.Arrays;
import java.util.Comparator;
public class ArraySorting {
public static void main(String[] args) {
int[] nums = {64, 25, 12, 22, 11};
// === BUBBLE SORT ===
int[] arr1 = nums.clone();
bubbleSort(arr1);
System.out.println("Bubble: " + Arrays.toString(arr1));
// === SELECTION SORT ===
int[] arr2 = nums.clone();
selectionSort(arr2);
System.out.println("Selection: " + Arrays.toString(arr2));
// === INSERTION SORT ===
int[] arr3 = nums.clone();
insertionSort(arr3);
System.out.println("Insertion: " + Arrays.toString(arr3));
// === BUILT-IN Arrays.sort() ===
int[] arr4 = nums.clone();
Arrays.sort(arr4); // ✅ Use this in production!
System.out.println("Arrays.sort: " + Arrays.toString(arr4));
// === SORT RANGE ===
int[] arr5 = nums.clone();
Arrays.sort(arr5, 1, 4); // Sort indices 1-3 only
System.out.println("Partial: " + Arrays.toString(arr5));
// === SORT OBJECTS ===
String[] names = {"Charlie", "Alice", "Bob"};
Arrays.sort(names); // Alphabetical
System.out.println("Names: " + Arrays.toString(names));
// === REVERSE ORDER ===
Integer[] integers = {5, 2, 8, 1, 9};
Arrays.sort(integers, Comparator.reverseOrder());
System.out.println("Descending: " + Arrays.toString(integers));
// === PARALLEL SORT (large arrays) ===
int[] large = new int[1000000];
// Fill with random values...
Arrays.parallelSort(large); // Multithreaded for large data
}
// Bubble Sort - O(N²)
static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// Swap
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
// Selection Sort - O(N²)
static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIdx]) {
minIdx = j;
}
}
// Swap min with current
int temp = arr[minIdx];
arr[minIdx] = arr[i];
arr[i] = temp;
}
}
// Insertion Sort - O(N²)
static 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;
}
}
}⚠️ Common Mistakes
Mistake #1: Using O(N²) for large data
// ❌ Slow for 100,000+ elements
bubbleSort(largeArray);
// ✅ Use Arrays.sort()
Arrays.sort(largeArray);Mistake #2: Forgetting primitives can't use Comparator
int[] nums = {5, 2, 8};
Arrays.sort(nums, Comparator.reverseOrder()); // ❌ Compile error!
// Use Integer[] wrapper or manual reverse4. The "Interview Corner"
🏆 Q1: "What sort does Arrays.sort() use?" Answer: Dual-Pivot QuickSort for primitives, TimSort (merge+insertion hybrid) for objects. Both O(N log N).
🏆 Q2: "What's a stable sort?" Answer: Maintains relative order of equal elements. Merge and Insertion are stable; Quick and Selection are not.
🏆 Q3: "When is Bubble Sort useful?" Answer: Almost never—only for teaching or nearly-sorted tiny arrays. Use Arrays.sort() in production.
🎓 Key Takeaways
✅ Use Arrays.sort() for production code
✅ O(N²) algorithms for learning only
✅ parallelSort() for very large arrays
✅ Use Comparator for custom ordering
✅ Know Big O for interviews!