Explore advanced sorting algorithms that leverage divide and conquer strategies. Master efficient approaches for sorting large datasets with better time complexity.
| Algorithm | Time Complexity (Best) | Time Complexity (Average) | Time Complexity (Worst) | Space Complexity | Stability |
|---|---|---|---|---|---|
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Stable |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | Unstable |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | Unstable |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Stable |
public class MergeSort {
public static void mergeSort(int[] arr) {
if (arr.length < 2) {
return;
}
int mid = arr.length / 2;
int[] left = new int[mid];
int[] right = new int[arr.length - mid];
// Populate the left and right arrays
for (int i = 0; i < mid; i++) {
left[i] = arr[i];
}
for (int i = mid; i < arr.length; i++) {
right[i - mid] = arr[i];
}
// Recursive calls
mergeSort(left);
mergeSort(right);
// Merge the sorted left and right arrays
merge(arr, left, right);
}
private static void merge(int[] arr, int[] left, int[] right) {
int leftIndex = 0;
int rightIndex = 0;
int targetIndex = 0;
// Compare elements from left and right and place the smaller one in the target array
while (leftIndex < left.length && rightIndex < right.length) {
if (left[leftIndex] <= right[rightIndex]) {
arr[targetIndex++] = left[leftIndex++];
} else {
arr[targetIndex++] = right[rightIndex++];
}
}
// Copy remaining elements from left array (if any)
while (leftIndex < left.length) {
arr[targetIndex++] = left[leftIndex++];
}
// Copy remaining elements from right array (if any)
while (rightIndex < right.length) {
arr[targetIndex++] = right[rightIndex++];
}
}
// Example usage
public static void main(String[] args) {
int[] array = {38, 27, 43, 3, 9, 82, 10};
System.out.println("Before sorting:");
printArray(array);
mergeSort(array);
System.out.println("After sorting:");
printArray(array);
}
private static void printArray(int[] arr) {
for (int i : arr) {
System.out.print(i + " ");
}
System.out.println();
}
}public class QuickSort {
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
// Find the partition index
int partitionIndex = partition(arr, low, high);
// Sort the elements before and after the partition index
quickSort(arr, low, partitionIndex - 1);
quickSort(arr, partitionIndex + 1, high);
}
}
private static int partition(int[] arr, int low, int high) {
// Select the rightmost element as pivot
int pivot = arr[high];
// Index of smaller element
int i = low - 1;
for (int j = low; j < high; j++) {
// If current element is smaller than or equal to pivot
if (arr[j] <= pivot) {
i++;
// Swap arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// Swap arr[i+1] and arr[high] (put the pivot in its correct position)
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
// Return the position of the pivot
return i + 1;
}
// Optimization: Random pivot selection
private static int partitionWithRandomPivot(int[] arr, int low, int high) {
// Generate a random pivot index
int randomIndex = low + (int) Math.random() % (high - low + 1);
// Swap the random element with the high element
int temp = arr[randomIndex];
arr[randomIndex] = arr[high];
arr[high] = temp;
// Call the standard partition method
return partition(arr, low, high);
}
// Example usage
public static void main(String[] args) {
int[] array = {10, 7, 8, 9, 1, 5};
System.out.println("Before sorting:");
printArray(array);
quickSort(array, 0, array.length - 1);
System.out.println("After sorting:");
printArray(array);
}
private static void printArray(int[] arr) {
for (int i : arr) {
System.out.print(i + " ");
}
System.out.println();
}
}For additional hands-on practice and in-depth exercises on advanced sorting algorithms, check out our comprehensive guided project:
Implement the sorting algorithms discussed in the lecture:
You can access the coding exercises on LeetCode - Sort an Array
Improve the sorting algorithms with optimization techniques:
Test your optimized algorithms on various input types (already sorted, reverse sorted, random)
Apply sorting algorithms to solve practical problems: