Fastest Sorting Algorithm Java

Shubham Vora Oct 12, 2023
  1. Counting Sort Algorithm in Java
  2. Merge Sort Algorithm in Java
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 freq array of size range to store the frequency of every element.
  • Iterate through the original array and store the frequency of every element in the freq array.
  • 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 freq array.
  • 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]++;
    }
    // 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 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 Vora avatar Shubham Vora avatar

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.

LinkedIn GitHub

Related Article - Java Sort