Learn to implement and apply advanced sorting algorithms: Merge Sort and Quick Sort.
public static int[] mergeSort(int[] arr) {
if (arr.length <= 1) {
return arr;
}
int mid = arr.length / 2;
int[] left = Arrays.copyOfRange(arr, 0, mid);
int[] right = Arrays.copyOfRange(arr, mid, arr.length);
return merge(mergeSort(left), mergeSort(right));
}
public static int[] merge(int[] left, int[] right) {
int[] result = new int[left.length + right.length];
int i = 0, j = 0, k = 0;
while (i < left.length && j < right.length) {
if (left[i] < right[j]) {
result[k++] = left[i++];
} else {
result[k++] = right[j++];
}
}
while (i < left.length) {
result[k++] = left[i++];
}
while (j < right.length) {
result[k++] = right[j++];
}
return result;
}
int[] numbers = {38, 27, 43, 3, 9, 82, 10};
System.out.println(Arrays.toString(mergeSort(numbers))); // [3, 9, 10, 27, 38, 43, 82]
public static int[] quickSort(int[] arr, int left, int right) {
if (left < right) {
int pivotIndex = partition(arr, left, right);
quickSort(arr, left, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, right);
}
return arr;
}
public static int partition(int[] arr, int left, int right) {
int pivot = arr[right];
int i = left - 1;
for (int j = left; j < right; j++) {
if (arr[j] <= pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[right];
arr[right] = temp;
return i + 1;
}
int[] numbers = {10, 7, 8, 9, 1, 5};
System.out.println(Arrays.toString(quickSort(numbers, 0, numbers.length - 1))); // [1, 5, 7, 8, 9, 10]
| Characteristic | Merge Sort | Quick Sort |
|---|---|---|
| Approach | Divide and conquer, merges sorted sublists | Divide and conquer, uses pivot to partition |
| Time Complexity | O(n log n) - consistent | Average: O(n log n), Worst: O(n²) |
| Space Complexity | O(n) - requires extra space | O(log n) - in-place partitioning |
| Stability | Stable (preserves order of equal elements) | Unstable (may change order of equal elements) |
| Best Use Cases | External sorting, linked lists, stability required | Internal sorting, arrays, memory constraints |
Test your understanding with these LeetCode problems: