Scribd
Upload
28 views2 pages

Best Sorting Algorithms Java

The document outlines three sorting algorithms in Java: Quick Sort, Merge Sort, and Tim Sort. Quick Sort has a worst-case time complexity of O(n^2) and is not stable, while Merge Sort and Tim Sort have a worst-case time complexity of O(n log n) and are stable. Each algorithm is accompanied by its implementation in Java code.

Uploaded by

arunappu7623
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
28 views2 pages

Best Sorting Algorithms Java

The document outlines three sorting algorithms in Java: Quick Sort, Merge Sort, and Tim Sort. Quick Sort has a worst-case time complexity of O(n^2) and is not stable, while Merge Sort and Tim Sort have a worst-case time complexity of O(n log n) and are stable. Each algorithm is accompanied by its implementation in Java code.

Uploaded by

arunappu7623
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

Best Sorting Algorithms in Java

Quick Sort
Best Case: O(n log n)
Average Case: O(n log n)
Worst Case: O(n^2)
Space Case: O(log n)
Stable Case: No

void quickSort(int[] arr, int low, int high) {


if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}

int partition(int[] arr, int low, int high) {


int pivot = arr[high];
int i = (low - 1);
for (int j = low; j < high; 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[high];
arr[high] = temp;
return i + 1;
}

Merge Sort
Best Case: O(n log n)
Average Case: O(n log n)
Worst Case: O(n log n)
Space Case: O(n)
Stable Case: Yes

void mergeSort(int[] arr, int l, int r) {


if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}

void merge(int[] arr, int l, int m, int r) {


int n1 = m - l + 1;
int n2 = r - m;
int[] L = new int[n1];
int[] R = new int[n2];
for (int i = 0; i < n1; i++) L[i] = arr[l + i];
for (int j = 0; j < n2; j++) R[j] = arr[m + 1 + j];
int i = 0, j = 0, k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) arr[k++] = L[i++];
else arr[k++] = R[j++];
}
while (i < n1) arr[k++] = L[i++];
while (j < n2) arr[k++] = R[j++];
}

Tim Sort (Java Arrays.sort)


Best Case: O(n)
Average Case: O(n log n)
Worst Case: O(n log n)
Space Case: O(n)
Stable Case: Yes

// Uses Arrays.sort() in Java which is a hybrid of Merge Sort and Insertion Sort
import java.util.Arrays;

int[] arr = {5, 3, 8, 6, 2};


Arrays.sort(arr); // Tim Sort (Stable and efficient)

You might also like