# Fastest Sorting Algorithm Java

Shubham Vora Nov 15, 2022

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.

• ##### Store all sorted elements from `result` to 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]++;
}
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.

• ##### If any element remains in the `LeftArray`, store them in the original array, and do the same for the `RightArray`.

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.

Author: Shubham Vora

Shubham is a software developer interested in learning and writing about various technologies. He loves to help people by sharing vast knowledge about modern technologies via different platforms such as the DelftStack.com website.