What is Sorting?
Sorting means arranging data in a specific, meaningful order, usually ascending (small to large) or descending (large to small).
It is one of the most important concepts in computer science because it helps in organizing, searching, and analyzing data efficiently.
For example, when you open your phone’s contact list, names appear alphabetically, that’s sorting in action!
Advanced Sorting Techniques in Java
- Merge Sort
- Quick Sort
- Heap Sort
- Counting Sort
- Radix Sort
- Bucket Sort
These sorting techniques are more efficient than basic algorithms like Bubble Sort or Insertion Sort, especially for large datasets.
1) Merge Sort
Merge Sort is one of the most efficient sorting algorithms used in Java. It works on the Divide and Conquer principle, meaning it divides the array into smaller parts, sorts each part, and then merges them back together in the correct order.
Code Example:
import java.util.Arrays;
public class MergeSortDemo {
// Function to divide and sort the array
public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int middle = (left + right) / 2;
// Sort both halves recursively
mergeSort(arr, left, middle);
mergeSort(arr, middle + 1, right);
// Merge the sorted halves
merge(arr, left, middle, right);
}
}
// Function to merge two sorted parts
public static void merge(int[] arr, int left, int mid, int right) {
// Find sizes of the two subarrays
int leftSize = mid - left + 1;
int rightSize = right - mid;
// Create temporary arrays
int[] leftArr = new int[leftSize];
int[] rightArr = new int[rightSize];
// Copy data into temporary arrays
for (int i = 0; i < leftSize; i++)
leftArr[i] = arr[left + i];
for (int j = 0; j < rightSize; j++)
rightArr[j] = arr[mid + 1 + j];
// Merge both arrays back into main array
int i = 0, j = 0, k = left;
while (i < leftSize && j < rightSize) {
if (leftArr[i] <= rightArr[j]) {
arr[k++] = leftArr[i++];
} else {
arr[k++] = rightArr[j++];
}
}
// Copy remaining elements if any
while (i < leftSize) {
arr[k++] = leftArr[i++];
}
while (j < rightSize) {
arr[k++] = rightArr[j++];
}
}
public static void main(String[] args) {
int[] numbers = {42, 15, 23, 8, 16, 4};
System.out.println("Original Array: " + Arrays.toString(numbers));
mergeSort(numbers, 0, numbers.length - 1);
System.out.println("Sorted Array: " + Arrays.toString(numbers));
}
}
Output:
Original Array: [42, 15, 23, 8, 16, 4]
Sorted Array: [4, 8, 15, 16, 23, 42]
2) Quick Sort
Quick Sort is another divide-and-conquer sorting algorithm, similar to Merge Sort, but instead of splitting in half, it chooses a pivot element and partitions the array into two parts:
- Elements less than the pivot go to the left.
- Elements greater than the pivot go to the right.
Code Example:
import java.util.Arrays;
public class QuickSortDemo {
// Function to perform Quick Sort
public static void quickSort(int[] arr, int start, int end) {
if (start < end) {
int pivotIndex = partition(arr, start, end);
// Recursively sort left and right subarrays
quickSort(arr, start, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, end);
}
}
// Partition the array using last element as pivot
public static int partition(int[] arr, int start, int end) {
int pivot = arr[end]; // Pivot element
int i = start - 1; // Index of smaller element
for (int j = start; j < end; j++) {
if (arr[j] < pivot) {
i++;
swap(arr, i, j);
}
}
// Place pivot at correct position
swap(arr, i + 1, end);
return i + 1;
}
// Helper method to swap two elements
private static void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
public static void main(String[] args) {
int[] numbers = {34, 7, 23, 32, 5, 62};
System.out.println("Original Array: " + Arrays.toString(numbers));
quickSort(numbers, 0, numbers.length - 1);
System.out.println("Sorted Array: " + Arrays.toString(numbers));
}
}
Output:
Original Array: [34, 7, 23, 32, 5, 62]
Sorted Array: [5, 7, 23, 32, 34, 62]
3) Heap Sort
Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure to sort elements. It works in two main steps:
- Extract the Largest Element – Swap it with the last element, and reduce the heap size. Repeat until the array is sorted.
- Build a Max Heap – Arrange the array so the largest element is at the root.
Code Example:
import java.util.Arrays;
public class HeapSortDemo {
// Function to perform Heap Sort
public static void heapSort(int[] arr) {
int n = arr.length;
// Step 1: Build a max heap
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// Step 2: Extract elements from heap
for (int i = n - 1; i > 0; i--) {
swap(arr, 0, i); // Move current largest to end
heapify(arr, i, 0); // Heapify reduced heap
}
}
// Heapify a subtree rooted at index i
private static void heapify(int[] arr, int heapSize, int i) {
int largest = i; // Initialize largest as root
int leftChild = 2 * i + 1; // Left child index
int rightChild = 2 * i + 2; // Right child index
// Check if left child is larger
if (leftChild < heapSize && arr[leftChild] > arr[largest]) {
largest = leftChild;
}
// Check if right child is larger
if (rightChild < heapSize && arr[rightChild] > arr[largest]) {
largest = rightChild;
}
// Swap and continue heapifying if root is not largest
if (largest != i) {
swap(arr, i, largest);
heapify(arr, heapSize, largest);
}
}
// Helper method to swap two elements
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args) {
int[] numbers = {20, 5, 15, 22, 3};
System.out.println("Original Array: " + Arrays.toString(numbers));
heapSort(numbers);
System.out.println("Sorted Array: " + Arrays.toString(numbers));
}
}
Output:
Original Array: [20, 5, 15, 22, 3]
Sorted Array: [3, 5, 15, 20, 22]
4. Counting Sort
Counting Sort is a non-comparison-based sorting algorithm. It works best for integers or elements within a known range. The idea is to count the frequency of each element and then reconstruct the sorted array.
Code example:
import java.util.Arrays;
public class CountingSortDemo {
public static void countingSort(int[] arr) {
int max = Arrays.stream(arr).max().orElse(0);
int[] count = new int[max + 1];
// Count occurrences
for (int num : arr) {
count[num]++;
}
// Reconstruct the sorted array
int index = 0;
for (int i = 0; i < count.length; i++) {
while (count[i] > 0) {
arr[index++] = i;
count[i]--;
}
}
}
public static void main(String[] args) {
int[] array = {4, 2, 2, 8, 3, 3, 1};
System.out.println("Original: " + Arrays.toString(array));
countingSort(array);
System.out.println("Sorted: " + Arrays.toString(array));
}
}
Output:
Original: [4, 2, 2, 8, 3, 3, 1]
Sorted: [1, 2, 2, 3, 3, 4, 8]5. Radix Sort
Radix Sort sorts numbers digit by digit, starting from the least significant digit (LSD) to the most significant digit (MSD). It is efficient for large sets of integers.
Code example:
import java.util.Arrays;
public class RadixSortDemo {
public static void radixSort(int[] arr) {
int max = Arrays.stream(arr).max().orElse(0);
for (int exp = 1; max / exp > 0; exp *= 10) {
countingSortByDigit(arr, exp);
}
}
private static void countingSortByDigit(int[] arr, int exp) {
int n = arr.length;
int[] output = new int[n];
int[] count = new int[10];
// Count occurrences of digits
for (int num : arr) {
int digit = (num / exp) % 10;
count[digit]++;
}
// Cumulative count
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
// Build output array
for (int i = n - 1; i >= 0; i--) {
int digit = (arr[i] / exp) % 10;
output[count[digit] - 1] = arr[i];
count[digit]--;
}
// Copy to original array
System.arraycopy(output, 0, arr, 0, n);
}
public static void main(String[] args) {
int[] array = {170, 45, 75, 90, 802, 24, 2, 66};
System.out.println("Original: " + Arrays.toString(array));
radixSort(array);
System.out.println("Sorted: " + Arrays.toString(array));
}
}
Output:
Original: [170, 45, 75, 90, 802, 24, 2, 66]
Sorted: [2, 24, 45, 66, 75, 90, 170, 802]6. Bucket Sort
Bucket Sort distributes elements into buckets, sorts each bucket individually, and then merges them. Ideal for uniformly distributed data like decimals between 0 and 1.
Code example:
import java.util.*;
public class BucketSortDemo {
public static void bucketSort(double[] arr) {
int n = arr.length;
List<Double>[] buckets = new List[n];
// Create empty buckets
for (int i = 0; i < n; i++) {
buckets[i] = new ArrayList<>();
}
// Distribute elements into buckets
for (double num : arr) {
int bucketIndex = (int) (num * n);
buckets[bucketIndex].add(num);
}
// Sort individual buckets and merge
int index = 0;
for (List<Double> bucket : buckets) {
Collections.sort(bucket);
for (double num : bucket) {
arr[index++] = num;
}
}
}
public static void main(String[] args) {
double[] array = {0.42, 0.32, 0.23, 0.52, 0.25, 0.47};
System.out.println("Original: " + Arrays.toString(array));
bucketSort(array);
System.out.println("Sorted: " + Arrays.toString(array));
}
}
Output:
Original: [0.42, 0.32, 0.23, 0.52, 0.25, 0.47]
Sorted: [0.23, 0.25, 0.32, 0.42, 0.47, 0.52]