Sorting algorithms are fundamental tools in computer science used to organize data efficiently. Sorting algorithms are techniques used to rearrange elements in a list or array in a specific order. The order could be ascending or descending based on certain criteria, such as numerical value or alphabetical order. Sorting algorithms play a crucial role in various applications, including databases, search algorithms, and more.

In Java, sorting algorithms can be implemented using various approaches, each with its unique characteristics and performance implications. In Java, there are various sorting algorithms, each with its advantages and disadvantages. In this guide, we’ll explore some of the most commonly used sorting algorithms, including their implementations, complexities, and use cases.

Sorting algorithms in Java : Insertion Sort

Insertion Sort is a simple sorting algorithm that builds the final sorted array one element at a time. It iterates through the input array, removing one element per iteration and then finding its correct position in the sorted array.

public int[] insertionSort(int[] list) {
   
  int i;   // Counter for outer loop
  int j;   // Counter for inner loop

  int key;    // To hold the key value purpose we use it 

  int temp;   // It will be helpful while swapping values 

  for(i = 1; i < list.length; i++) {
     // Outer for loop starts with 1 and checks till the end value.
     // Here we consider the 0th element is already sorted that's why we start from 1
  
     key = list[i];   // It is our key value which is list[i] for every iteration  
     j = i - 1;         // It will start point of comparison moving downwards till 0 
   
     // We end the while loop when j value reaches 0 or when the key value is no longer smaller than the value
     while(j >= 0 && key < list[j]) {
       // Swap the values using the temp variable and arrange them in increasing order        
       temp = list[j];
       list[j] = list[j + 1];
       list[j + 1] = temp;
       j--;     // Decreasing j by 1 as we move towards the left 
     }

   }
   
  return list;
}

This insertionSort method implements the insertion sort algorithm for sorting an array of integers in increasing order. It iterates through the array, considering each element as a key and inserting it into the correct position in the sorted subarray to its left. The inner loop compares the key with the elements to its left and swaps them if necessary to maintain the sorted order. Finally, it returns the sorted array.

Explanation

Given an array of integers, sort them in increasing order using insertion sort:

Initial array: 5, 8, 1, 3, 9, 6

Definition of sorted: All items to the left are smaller. For example, 5 is already considered sorted as there are no elements to its left.

So, we start our insertion sort process from index 1:

1. Key (k) = 8. Compare k < 5? No. So, 8’s position is correct. Consider 5 and 8 as sorted.
2. Next, at index 2:
   • Key (k) = 1.
   • Compare k < 8? Yes, swap: 5, 1, 8, 3, 9, 6.
   • Compare k < 5? Yes, swap: 1, 5, 8, 3, 9, 6.
   • Element till index 2 is sorted.
3. Start at index 3:
   • Key (k) = 3.
   • Compare k < 8? Yes, swap: 1, 5, 3, 8, 9, 6.
   • Compare k < 5? Yes, swap: 1, 3, 5, 8, 9, 6.
   • Compare k < 1? No, no swap.
   • Elements till index 3 are now sorted.
4. Start at index 4:
   • Key (k) = 9.
   • Compare k < 8? No, no swap. Also, all elements left of 8 are sorted, indicating 9’s position is correct.
   • Elements till index 4 are also sorted.
5. Start at index 5:
   • Key (k) = 6.
   • Compare k < 9? Yes, swap: 1, 3, 5, 8, 6, 9.
   • Compare k < 8? Yes, swap: 1, 3, 5, 6, 8, 9.
   • Compare k < 5? No, no swap. End of loop.

Finally, we obtain the sorted list using insertion sort. Final array: {1, 3, 5, 6, 8, 9}

Note: Insertion Sort is not a fast sorting algorithm as it uses nested loops to shift items into place. It is useful only for small datasets. It runs in O(n^2) time complexity and O(1) space complexity.

Selection Sort

Selection Sort is a simple sorting algorithm that repeatedly selects the smallest (or largest) element from the unsorted part of the array and moves it to the beginning. This process continues until the entire array is sorted.

public int[] selectionSort(int[] list) {
    int i; // Outer loop counter
    int j; // Inner loop counter
    int minValue; // To track minimum value
    int minIndex; // To track the index of the minimum value in the array
    int temp = 0; // For swapping purposes

    // Let's consider this array: 7, 8, 5, 4, 9, 2

    // Outer loop should iterate from 0 to 5 (i.e., 6 iterations)
    // So the outer loop should be: for i = 0 to 5
    for (i = 0; i < list.length; i++) {
        // Initialize minValue and minIndex to the first unsorted item each time through the outer loop
        minValue = list[i];
        minIndex = i;

        // Inner loop starts at the first unsorted item and continues through the last item in the list
        // So the inner loop should be: for j = i to 5
        for (j = i; j < list.length; j++) {
            // Inside the inner loop, if the list item is less than the current minValue,
            // update minValue and store its index in minIndex
            if (list[j] < minValue) {
                minValue = list[j];
                minIndex = j;
            }
        }

        // After that, we check if the minValue is less than the value at the current index of the outer loop
        // If yes, then swap that value with the value at minIndex
        if (minValue < list[i]) {
            temp = list[i];
            list[i] = list[minIndex];
            list[minIndex] = temp;
        }
    }
    return list;
}

This selectionSort method implements the selection sort algorithm for sorting an array of integers in increasing order. It iterates through the array, finding the minimum element in the unsorted part of the array and swapping it with the first unsorted element. This process repeats until the entire array is sorted. Finally, it returns the sorted array.

Explanation

Selection Sort: It finds the smallest item from the unsorted part of the list and moves it to the first element of the list while performing selection sort.

Consider this array: 7, 8, 5, 4, 9, 2 // also imagine indices from 0 to 5.

So initially, our minValue is 7 and minIndex is 0.

• Now, comparison:
  • Is 8 < minValue (7)? No.
  • Is 5 < minValue (7)? Yes, the new minValue is 5 and minIndex is 2.
  • Is 4 < minValue (5)? Yes, the new minValue is 4 and minIndex is 3.
  • Is 9 < minValue (4)? No. Is 2 < minValue (4)? Yes, the new minValue is 2 and minIndex is 5.

We found our first smallest element, so we swap that element with the first element ==> 2, 8, 5, 4, 9, 7.

• Our second iteration starts with index 1, so our first element is 8, and minValue is 8, with minIndex as 1. Now, start comparison toward the right side of 8.
  • Is 5 < minValue (8)? Yes, the new minValue is 5, and minIndex is 2.
  • Is 4 < minValue (5)? Yes, the new minValue is 4, and minIndex is 3.
  • Is 9 < minValue (4)? No.
  • Is 7 < minValue (4)? No.

We found our smallest element for the second iteration, so we swap it with the first element ==> 2, 4, 5, 8, 9, 7.

• Now, start comparison towards the right side of 5, and we see that 5 is the smallest element among them, so there’s no need to swap.

• Again, we start comparison towards the right side of 8. So, minValue is 8, and minIndex is 3.
  • Is 9 < minValue (8)? No.
  • Is 7 < minValue (8)? Yes, the new minValue is 7, and minIndex is 5.

So, swap ==> 2, 4, 5, 7, 9, 8.

• Now, for the next iteration, minValue is 9, and minIndex is 4.
  • Is 8 < minValue (9)? Yes, the new minValue is 8, and minIndex is 5.

So, swap ==> 2, 4, 5, 7, 8, 9.

Note: Selection Sort is not a fast sorting algorithm because it uses nested loops to sort. It is useful only for small datasets means suitable for small arrays or when auxiliary memory is limited. It runs in O(n^2) time complexity and O(1) space complexity.

Bubble Sort

Bubble Sort is another simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted.

public int[] bubbleSort(int[] list) {
    int i; // outer loop counter
    int j; // inner loop counter
    int temp = 0; // for swapping purpose

    for (i = 0; i < list.length - 1; i++) { // outer loop iterate till the end
        for (j = 0; j < list.length - 1 - i; j++) { // inner loop iterate till the end where already sorted element bubbled at the end
            if (list[j] > list[j + 1]) { // if we consider two adjacent values then previous value greater means we need to swap them with next value
                temp = list[j];
                list[j] = list[j + 1];
                list[j + 1] = temp;
            }
        }
    }
    return list;
}

This bubbleSort method implements the bubble sort algorithm for sorting an array of integers in increasing order. It iterates through the array multiple times, comparing adjacent elements and swapping them if they are in the wrong order. This process repeats until the array is sorted. Finally, it returns the sorted array.

Explanation

Bubble Sort: It is a simple sorting algorithm that repeatedly compares adjacent elements in the list and swaps them if they are in the wrong order. This process continues until the list is sorted.

Unsorted list: 5, 8, 1, 6, 9, 2 // Imagine indices from 0 to 5.

So, what is bubble sort?

In bubble sort, we repeatedly compare adjacent items, for example, 5 and 8, so that with every iteration, larger items “bubble” to the right side.

• First iteration:
  • Is 5 > 8? No.
    • Is 8 > 1? Yes ==> Swap ==> 5, 1, 8, 6, 9, 2
      • Is 8 > 6? Yes ==> Swap ==> 5, 1, 6, 8, 9, 2
        • Is 8 > 9? No.
          • Is 9 > 2? Yes ==> Swap ==> 5, 1, 6, 8, 2, 9

• Second iteration:
  • Is 5 > 1? Yes ==> Swap ==> 1, 5, 6, 8, 2, 9
    • Is 5 > 6? No.
      • Is 6 > 8? No.
        • Is 8 > 2? Yes ==> Swap ==> 1, 5, 6, 2, 8, 9

• Third iteration:
  • Is 1 > 5? No.
    • Is 5 > 6? No.
      • Is 6 > 2? Yes ==> Swap ==> 1, 5, 2, 6, 8, 9
        • Is 6 > 8? No.
          • Is 8 > 9? No.

• Fourth Iteration:
  • Is 1 > 5? No.
    • Is 5 > 2? Yes ==> Swap ==> 1, 2, 5, 6, 8, 9
      • Is 5 > 6? No.
        • Is 6 > 8? No.
          • Is 8 > 9? No.

• Fifth Iteration:
  • All elements are in sorted order; no need to do any swapping.

Final sorted list: 1, 2, 5, 6, 8, 9

Note: Bubble Sort is not an efficient sorting algorithm because it uses nested loops. It is useful only for small data sets. It runs in O(n^2) and O(1) space complexity.

Merge Sort

Merge Sort is a divide-and-conquer algorithm that divides the input array into two halves, sorts each half separately, and then merges the sorted halves.

// passing low and high index to this function
// e.g 38,27,43,3,9,82,10 ==> low -> 0 and high -> 6 (size - 1)th index
private void mergeSort(int low, int high) {
    if (low < high)      // base condition
    {
        int mid = low + (high - low) / 2;    // we need to find mid (it is 3 here)
        // perform recursive division into low to mid and then mid + 1 to high
        mergeSort(low, mid);      // 38,27,43,3  ===for next recursive call ===> 38,27 and 43,3 === next recursive call ==> 38 and 27 | 43 and 3 here as we reached base condition where low and high are equal and return back and execute remaining code
        mergeSort(mid + 1, high);   // we start when the above statement executed completely and reached the base case, so now 9,82,10  === for the next recursive call ===> 9,82 and 10  ==== for the next call ===> 9 and 82 | 10 here also we reached the base condition so go back now
        merge(low, mid, high);    // it will just merge the elements according to the sorting order
    }
}

// we pass low, mid, and high value
private void merge(int low, int mid, int high) {
    // for copying purposes means we copy number values to helper[] from low to till high
    for (int i = low; i <= high; i++) {
        helper[i] = numbers[i];
    }

    int i = low;
    int j = mid + 1;
    int k = low;

    // we tried to sort the numbers[] element and placed them in exact same order
    while (i <= mid && j <= high) {
        if (helper[i] <= helper[j]) {
            numbers[k] = helper[i];
            i++;
        } else {
            numbers[k] = helper[j];
            j++;
        }
        k++;
    }

    // if still some values remain to be placed in sorted order in numbers[] we will do that here
    while (i <= mid) {
        numbers[k] = helper[i];
        k++;
        i++;
    }
}

These methods implement the merge sort algorithm. mergeSort is a recursive method that divides the array into two halves and recursively calls itself on each half until it reaches the base case where low is no longer less than high. Then, the merge method merges the two sorted halves into a single sorted array.

Explanation

Merge Sort is a divide and conquer algorithm. It divides the input array into two halves, recursively calls itself for the two halves, and then merges the two sorted halves.

For example, with an input array like 38, 27, 43, 3, 9, 82, 10:

First, we call mergeSort(0, 6) as the initial entry point.

In mergeSort:

• We find the mid index (low + (high – low) / 2) to split the array into two halves.
• Then, we recursively call mergeSort for the left half (low to mid) and the right half (mid + 1 to high).
• Finally, we merge the sorted halves using the merge function.

In merge:

• We create a helper array to copy elements from the original array.
• We iterate through the two halves, comparing elements and merging them into the original array in sorted order.
• If any elements remain in the left half after merging, we copy them back to the original array.

Let’s go through the merge sort algorithm step by step:

1. Initial array: {38, 27, 43, 3, 9, 82, 10}
2. Initial call to mergeSort(0, 6):
   • Since low (0) is less than high (6), we proceed.
   • Calculate mid = 0 + (6 – 0) / 2 = 3
3. Recursive call 1: mergeSort(0, 3)
   • Since low (0) is less than high (3), we proceed.
   • Calculate mid = 0 + (3 – 0) / 2 = 1
4. Recursive call 2a: mergeSort(0, 1)
   • Since low (0) is less than high (1), we proceed.
   • Calculate mid = 0 + (1 – 0) / 2 = 0
5. Recursive call 2b: mergeSort(1, 3)
   • Since low (1) is less than high (3), we proceed.
   • Calculate mid = 1 + (3 – 1) / 2 = 2
6. Recursive call 3: mergeSort(1, 2)
   • Since low (1) is less than high (2), we proceed.
   • Calculate mid = 1 + (2 – 1) / 2 = 1
7. Recursive call 4: mergeSort(2, 3)
   • Since low (2) is less than high (3), we proceed.
   • Calculate mid = 2 + (3 – 2) / 2 = 2
8. Back to Recursive call 4: merge(1, 1, 2)
   • Helper array: {27, 43, 43, 3, 9, 82, 10}
   • i = 1, j = 2, k = 1
   • Compare helper[i] (27) with helper[j] (43), place the smaller one (27) in numbers[k] (numbers[1]), increment i and k.
   • numbers: {38, 27, 43, 3, 9, 82, 10}
   • Increment k to 2 and i to 2.
9. Back to Recursive call 3: merge(1, 1, 3)
   • Helper array: {27, 38, 43, 3, 9, 82, 10}
   • i = 1, j = 3, k = 1
   • Compare helper[i] (27) with helper[j] (3), place the smaller one (3) in numbers[k] (numbers[1]), increment j and k.
   • numbers: {38, 3, 43, 3, 9, 82, 10}
   • Increment k to 2 and j to 4.
   • Compare helper[i] (27) with helper[j] (9), place the smaller one (9) in numbers[k] (numbers[2]), increment j and k.
   • numbers: {38, 3, 9, 3, 9, 82, 10}
   • Increment k to 3 and j to 5.
   • Compare helper[i] (27) with helper[j] (82), place the smaller one (27) in numbers[k] (numbers[3]), increment i and k.
   • numbers: {38, 3, 9, 27, 9, 82, 10}
   • Increment k to 4 and i to 2.
10. Back to Recursive call 2a: merge(0, 0, 1)
    • Helper array: {38, 38, 9, 27, 9, 82, 10}
    • i = 0, j = 1, k = 0
    • Compare helper[i] (38) with helper[j] (3), place the smaller one (3) in numbers[k] (numbers[0]), increment j and k.
    • numbers: {3, 3, 9, 27, 9, 82, 10}
    • Increment k to 1 and j to 2.
    • Compare helper[i] (38) with helper[j] (9), place the smaller one (9) in numbers[k] (numbers[1]), increment j and k.
    • numbers: {3, 9, 9, 27, 9, 82, 10}
    • Increment k to 2 and j to 3.
    • Compare helper[i] (38) with helper[j] (27), place the smaller one (27) in numbers[k] (numbers[2]), increment i and k.
    • numbers: {3, 9, 27, 27, 9, 82, 10}
    • Increment k to 3 and i to 1.
11. Back to Recursive call 1: merge(0, 1, 3)
    • Helper array: {3, 9, 27, 38, 9, 82, 10}
    • i = 0, j = 2, k = 0
    • Compare helper[i] (3) with helper[j] (9), place the smaller one (3) in numbers[k] (numbers[0]), increment i and k.
    • numbers: {3, 9, 27, 38, 9, 82, 10}
    • Increment k to 1 and i to 1.
    • Compare helper[i] (9) with helper[j] (27), place the smaller one (9) in numbers[k] (numbers[1]), increment i and k.
    • numbers: {3, 9, 27, 38, 9, 82, 10}
    • Increment k to 2 and i to 2.
    • Compare helper[i] (27) with helper[j] (38), place the smaller one (27) in numbers[k] (numbers[2]), increment j and k.
    • numbers: {3, 9, 27, 38, 9, 82, 10}
    • Increment k to 3 and j to 3.
12. Final array: {3, 9, 27, 38, 9, 82, 10}

This process continues until the entire array is sorted. The merge sort algorithm effectively divides the array into smaller segments, sorts them individually, and then merges them back together in sorted order.

Note: Merge Sort has a time complexity of O(n log n) in the average and worst cases, and O(n) in the best case, making it efficient for large datasets and O(n) space complexity.

Quick Sort

Quick Sort is another divide-and-conquer algorithm that picks an element as a pivot and partitions the array around the pivot. It then recursively sorts the subarrays.

private void quickSort(int low, int high) {
    int i = low, j = high;
    int pivot = numbers[low + (high - low) / 2];  // Choosing the pivot element

    // Partitioning the array
    while (i <= j) {
        // Finding element on the left side that should be on the right
        while (numbers[i] < pivot) {
            i++;
        }
        // Finding element on the right side that should be on the left
        while (numbers[j] > pivot) {
            j--;
        }

        // If we found a value on the left that should be on the right and vice versa, swap them
        if (i <= j) {
            exchange(i, j);
            i++;
            j--;
        }
    }

    // Recursively sort the left and right partitions
    if (low < j) {
        quickSort(low, j);
    }
    if (i < high) {
        quickSort(i, high);
    }
}

This quickSort method implements the Quick Sort algorithm. It chooses a pivot element (here, the middle element) and partitions the array into two sub-arrays such that elements less than the pivot are on the left, and elements greater than the pivot are on the right. It then recursively sorts the sub-arrays until the entire array is sorted. The exchange method is assumed to swap the values at two indices in the array.

Explanation

Quick Sort is a divide and conquer algorithm. In this algorithm, the original data is divided into two parts, sorted individually, and then combined.

suppose

{6,4,2,1,5,3} is an array where low is pointing to 0th index and high is pointing to last index.

means,

• Set low to 0 and high to array.length - 1, then pass these values to quickSort(low, high).
• Assign low to i, which is the left side counter of the pivot, and assign high to j, which is the right side counter of the pivot.
• Find the pivot. What is a pivot? A pivot is a point we consider while sorting. We arrange smaller values than the pivot to its left side and greater values to its right side. We can take any value as the pivot, but it’s best to take it randomly. Here, we use the middle element as the pivot.
• We will check i <= j. If low becomes greater than high, we stop our following checks: i) First, we check the left side of the pivot to find any greater value than the pivot. If we find such a value, we terminate the while loop. Otherwise, we iterate until we reach the pivot. Since we don’t have any problem with values smaller than the pivot (as those should be on the left side), we increment i and move towards the pivot to check the next value. ii) After completing the left side (either by complete check or finding a greater value, terminating the while loop), we look at the right side of the pivot. We apply the same logic: while(any value > pivot). If true, we decrement j. If we find any smaller value than the pivot, the while loop terminates. iii) So, in the above two cases, we find whether the left side of the pivot will contain any greater value than the pivot or whether the right side of the pivot will contain any smaller value than the pivot. Because we sort the values according to the pivot, if we find a smaller value to the right and a larger value to the left, we need to place them on their respective sides. For this purpose, we use another if() condition: if i is not greater than j, then only do we exchange the values. Finally, we increment i and decrement j.
• As we perform sorting according to the pivot, only small values are placed on the left side of the pivot and large values are placed on the right side. However, we notice that neither the left side nor the right side is sorted.

For example, with an array like 6, 4, 2, 1, 5, 3:

• We call quickSort(0, 5) initially, where low = 0 and high = 5.
• We select a pivot element, here we choose the middle element, which is 2.
• We partition the array around the pivot, ensuring that elements less than the pivot are on the left and elements greater than the pivot are on the right.
• We recursively call quickSort for the left and right partitions, ensuring that all elements are sorted individually.
• We repeat this process until the entire array is sorted.

Let’s go through the Quick Sort algorithm step by step:

1. Initial array: {6, 4, 2, 1, 5, 3}
2. Initial call to quickSort(0, 5):
   • i = 0, j = 5
   • Pivot = numbers[0 + (5 – 0) / 2] = numbers[2] = 2
3. While loop (i=0, j=5):
   • i moves from left to right until it finds a value greater than or equal to the pivot. (i stops at 4)
   • j moves from right to left until it finds a value less than or equal to the pivot. (j stops at 3)
   • Since i <= j, exchange(numbers[i], numbers[j]) is performed.
   • After exchange, array becomes {3, 4, 2, 1, 5, 6}
   • Increment i and decrement j (i = 1, j = 4)
4. While loop (i=1, j=4):
   • i moves until it finds a value greater than or equal to the pivot. (i stops at 4)
   • j moves until it finds a value less than or equal to the pivot. (j stops at 1)
   • Since i <= j, exchange(numbers[i], numbers[j]) is performed.
   • After exchange, array becomes {3, 1, 2, 4, 5, 6}
   • Increment i and decrement j (i = 2, j = 3)
5. While loop (i=2, j=3):
   • i moves until it finds a value greater than or equal to the pivot. (i stops at 2)
   • j moves until it finds a value less than or equal to the pivot. (j stops at 2)
   • Since i <= j, exchange(numbers[i], numbers[j]) is performed.
   • After exchange, array remains {3, 1, 2, 4, 5, 6}
   • Increment i and decrement j (i = 3, j = 1)
6. While loop termination (i=3, j=1):
   • i > j, so the while loop terminates.
7. Recursive call 1: quickSort(0, 1)
   • This is the left side partition.
   • i = 0, j = 1
   • Subarray: {3, 1}
   • Pivot = numbers[0] = 3
   • While loop terminates immediately as i > j.
8. Recursive call 2: quickSort(3, 5)
   • This is the right side partition.
   • i = 3, j = 5
   • Subarray: {4, 5, 6}
   • Pivot = numbers[3] = 4
   • While loop terminates immediately as i > j.
9. Final sorted array: {1, 2, 3, 4, 5, 6}

This process continues recursively until all partitions have size 1 or less, meaning the array is sorted. The Quick Sort algorithm effectively divides the array into smaller partitions, sorts them individually, and then combines them to get the sorted array.

Note: Quick Sort has a time complexity of O(n log n) in the average and best cases, and O(n^2) in the worst case. However, its average case performance is typically much better than other O(n^2) algorithms like Bubble Sort and Selection Sort. It has space complexity O(log n) to O(n). Also, Quick Sort is efficient and widely used, but it has a higher worst-case time complexity compared to Merge Sort.

Conclusion

In this guide, we’ve covered several sorting algorithms in Java, including Selection Sort, Bubble Sort, Insertion Sort, Merge Sort, and Quick Sort. Each algorithm has its advantages and disadvantages, and the choice of algorithm depends on factors such as the size of the dataset, memory constraints, and desired performance characteristics. By understanding these sorting algorithms, you can choose the most appropriate one for your specific use case and optimize the efficiency of your Java applications.