Fastest Sorting Algorithm Java
This article will cover the two fastest sorting algorithms and write their code in Java.
The first technique is the Counting Sort, which has some limitations. So, we will cover the Merge Sort algorithm also.
Counting Sort Algorithm in Java
The counting sort algorithm is one of the fastest sorting techniques that we can use when array elements are given within a specific range. It is not a comparison-based sorting technique, but it sorts the array by counting and storing the frequency of every array element.
In simple terms, it uses hashing to sort the array.
Users should follow the below algorithm for the counting sort.
-
Find the maximum and minimum elements of the array.
-
Next, find the range of the array using maximum and minimum elements and create a new
freqarray of size range to store the frequency of every element. -
Iterate through the original array and store the frequency of every element in the
freqarray. -
By adding the frequencies, count the cumulative frequencies for every element.
-
Start iterating to the original array from the end and put every element to its sorted position using the
freqarray. -
Store all sorted elements from
resultto the original array to make the original array sorted.
Example Code:
class CountingSort {
// function to find the maximum from the array
static int findMax(int arr[]) {
int maxi = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > maxi)
maxi = arr[i];
}
return maxi; // return maximum
}
// function to find the minimum from the array
static int findMin(int arr[]) {
int mini = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] < mini)
mini = arr[i];
}
return mini; // return minimum
}
static void cntSort(int[] arr) {
int maxi = findMax(arr);
int mini = findMin(arr);
// getting range from maximum and minimum elements of the array
int range = maxi - mini + 1;
// creating the array to store the frequency of elements
int freq[] = new int[range];
// resultant array
int result[] = new int[arr.length];
// counting frequency of elements and storing it to freq array
for (int i = 0; i < arr.length; i++) {
freq[arr[i] - mini]++;
}
// Doing addition of frequency
for (int i = 1; i < freq.length; i++) {
freq[i] += freq[i - 1];
}
// Putting every element of arr to its correct place based on the freq array
for (int i = arr.length - 1; i >= 0; i--) {
result[freq[arr[i] - mini] - 1] = arr[i];
freq[arr[i] - mini]--;
}
// Make arr array sorted by assigning elements from the result array
for (int i = 0; i < arr.length; i++) {
arr[i] = result[i];
}
}
public static void main(String[] args) {
int[] arr = {10, 20, -2, -4, 3, 40, 50, 30, 20, 10};
cntSort(arr);
System.out.println("Sorted Array using counting sort is ");
for (int a = 0; a < arr.length; a++) {
System.out.print(arr[a] + " ");
}
}
}
Output:
Sorted Array is -4 -2 3 10 10 20 20 30 40 50
Time Complexity of the Counting Sort Algorithm in Java
The time complexity for Counting Sort is of linear order as we are using a single for loop.
| Best Case | O(n+k) |
| Average Case | O(n+k) |
| Worst Case | O(n+k) |
Space Complexity of the Counting Sort Algorithm in Java
The space complexity for the counting sort is O(n) as we use the temporary array to store sorted elements.
Limitations of the Counting Sort Algorithm in Java
The counting sort technique is the fastest algorithm to sort elements of the array without any doubt, but it has some limitations.
Users can think about the scenario where the array length is very small, and the input range is too large, like millions. Even the Bubble Sort can perform better in such cases.
So, users can use it to sort the array in linear time when the input range is small.
Merge Sort Algorithm in Java
To overcome the limitations of the Counting Sort, users can use the Merge Sort technique.
The Merge Sort algorithm follows the divide-and-conquer approach. First, it divides the array into two halves, sorts it, and merges the sorted array.
To learn the full algorithm step by step, users can follow the below steps.
-
Find the middle point of the array.
-
Recursively call the
mergeSort()function for the first and second parts of the array. -
Call the
merge()function to merge the array. -
In the
merge()function, create two temp arrays of the same size as two parts of the array and store the array element to the corresponding temporary array. -
Iterate through the temporary arrays until both have unsorted elements, find the minimum element from both the array, store it in the original array, and keep moving.
-
If any element remains in the
LeftArray, store them in the original array, and do the same for theRightArray.
Example Code:
class Test {
// function to merge two sorted arrays
static void merge(int arr[], int left, int mid, int right) {
// sizes for temp arrays
int n1 = mid - left + 1;
int n2 = right - mid;
// temp arrays
int LeftArray[] = new int[n1];
int RigthArray[] = new int[n2];
// clone data to temp arrays
for (int i = 0; i < n1; ++i) LeftArray[i] = arr[left + i];
for (int j = 0; j < n2; ++j) RigthArray[j] = arr[mid + 1 + j];
int a = 0, b = 0;
// merging temp arrays to the original array
int k = left;
while (a < n1 && b < n2) {
if (LeftArray[a] <= RigthArray[b]) {
arr[k] = LeftArray[a];
a++;
} else {
arr[k] = RigthArray[b];
b++;
}
k++;
}
// If any elements are left in LeftArray, clone it to the original array
while (a < n1) {
arr[k] = LeftArray[a];
a++;
k++;
}
// If any elements are left in RightArray, clone it to the original array
while (b < n2) {
arr[k] = RigthArray[b];
b++;
k++;
}
}
static void mergeSort(int arr[], int left, int right) {
if (left < right) {
// Find the mid of the array using the left and right
int mid = left + (right - left) / 2;
// sort the first half of the array
mergeSort(arr, left, mid);
// sort the second half of the array
mergeSort(arr, mid + 1, right);
// sort both parts of the array and merge it
merge(arr, left, mid, right);
}
}
public static void main(String args[]) {
int[] arr = {10, 201, -22121, -412, 3, 212121, 50, 30, 20, 1021212};
mergeSort(arr, 0, arr.length - 1);
System.out.println("Sorted array using merge sort is");
for (int a = 0; a < arr.length; a++) {
System.out.print(arr[a] + " ");
}
}
}
Output:
Sorted array is -22121 -412 3 10 20 30 50 201 212121 1021212
Time Complexity of the Merge Sort Algorithm in Java
The time complexity for mergeSort() is O(nlogn), where n is the array’s length. Here, the time complexity of the merge() function is of O(n), and the time complexity of the mergeSort() function is O(logn) as we are making a recursive call for every half part of the array.
| Best Case | O(nlog(n)) |
| Average Case | O(nlog(n)) |
| Worst Case | O(nlog(n)) |
Space Complexity of the Merge Sort Algorithm in Java
The space complexity for the merge sort is of O(n) as we use the two temporary arrays to store un-sorted elements.
In this article, we have learned the counting sort algorithm, one of the fastest algorithms in Java, step by step with its example code. Also, to overcome the limitations of the counting sort, we have learned the merge sort, which will work for any input range.
