Sorting Comparison
| Algorithm | Best | Average | Worst | Space | Stable |
|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Merge Sort | O(n lg n) | O(n lg n) | O(n lg n) | O(n) | Yes |
| Quick Sort | O(n lg n) | O(n lg n) | O(n²) | O(lg n) | No |
Merge Sort — Divide and Conquer
public void mergeSort(int[] arr, int left, int right) {
if (left >= right) return;
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid); // Sort left half
mergeSort(arr, mid + 1, right); // Sort right half
merge(arr, left, mid, right); // Merge two halves
}
Chia mảng làm đôi → sort từng nửa → merge lại. Luôn O(n log n) nhưng cần O(n) extra space.
Quick Sort — Partition
public void quickSort(int[] arr, int low, int high) {
if (low >= high) return;
int pivot = partition(arr, low, high);
quickSort(arr, low, pivot - 1);
quickSort(arr, pivot + 1, high);
}
Chọn pivot → partition (nhỏ hơn bên trái, lớn hơn bên phải) → sort từng phần.
Key insight: Java dùng Dual-Pivot QuickSort cho primitives và TimSort (hybrid merge+insertion) cho objects. Biết khi nào dùng
Arrays.sort()vsCollections.sort()là đủ cho 99% trường hợp.