2026-02-098 min read

Sorting (Java)

Learn Sorting (Java) step by step with clear examples and exercises.

Why This Matters

Sorting is an essential concept in computer science as it helps manage large datasets efficiently, ensuring faster search operations, reduced memory usage, and improved overall performance of your programs. Understanding various sorting algorithms is crucial for interview preparation, real-world programming tasks, and debugging common sorting issues. In this lesson, we will explore different sorting algorithms in Java, their practical applications, and common mistakes to avoid.

Prerequisites

To follow this lesson, you should have a basic understanding of Java programming concepts such as variables, loops, arrays, and methods. Familiarity with data structures like linked lists and trees will also be beneficial but is not strictly necessary. Before diving into the sorting algorithms, let's review some key Java concepts:

Variables: Declare and initialize variables using different data types (e.g., int, float, String).
Loops: Use for, while, and do-while loops to iterate through arrays or perform repetitive tasks.
Arrays: Create and manipulate one-dimensional and multi-dimensional arrays in Java.
Methods: Define and call functions to organize code and reuse functionality.

Core Concept

Sorting Algorithms (More Detailed Explanation)

Java provides several built-in sorting algorithms, each with its advantages and disadvantages in terms of time complexity, space complexity, and stability. Here are some commonly used sorting algorithms:

Bubble Sort: Simple algorithm that repeatedly swaps adjacent elements if they are in the wrong order. It has a worst-case and average time complexity of O(n^2), making it inefficient for large datasets. However, bubble sort is useful for small arrays or when implemented optimally (e.g., using a modified version called "optimized bubble sort").

void bubbleSort(int arr[]) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// Swap arr[j] and arr[j+1]
}
}
}
}

Selection Sort: Algorithm that finds the smallest element in the unsorted portion of the array and places it at the beginning. It has a worst-case and average time complexity of O(n^2), but it is more efficient than bubble sort for some cases due to its simpler implementation.

void selectionSort(int arr[]) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// Swap arr[i] and arr[minIndex]
}
}

Insertion Sort: Algorithm that builds a sorted array one element at a time by repeatedly inserting elements into their correct position in the sorted portion of the array. It has a worst-case and average time complexity of O(n^2), but it is more efficient than bubble sort and selection sort for small datasets due to its simpler implementation.

void insertionSort(int arr[]) {
int n = arr.length;
for (int i = 1; i < n; ++i) {
int key = arr[i];
int j = i - 1;

while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}

Merge Sort: Divide-and-conquer algorithm that splits the unsorted array into smaller subarrays, sorts them recursively, and merges the sorted subarrays back together. It has a worst-case time complexity of O(n log n), making it more efficient than bubble sort, selection sort, and insertion sort for large datasets.

void mergeSort(int arr[], int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}

void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;

int L[] = new int[n1];
int R[] = new int[n2];

for (int i = 0; i < n1; ++i) {
L[i] = arr[left + i];
}
for (int j = 0; j < n2; ++j) {
R[j] = arr[mid + 1 + j];
}

int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k++] = L[i++];
} else {
arr[k++] = R[j++];
}
}

while (i < n1) {
arr[k++] = L[i++];
}

while (j < n2) {
arr[k++] = R[j++];
}
}

Quick Sort: Another divide-and-conquer algorithm that selects a pivot element and partitions the array around it, recursively sorting the subarrays on either side of the pivot. It has an average time complexity of O(n log n), but its worst-case time complexity is O(n^2) if the pivot selection is poor.

void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}

int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j <= high - 1; j++) {
if (arr[j] < pivot) {
i++;
// Swap arr[i] and arr[j]
}
}
// Swap arr[i+1] and arr[high]
return (i + 1);
}

Sorting Libraries (More Detailed Explanation)

Java provides several libraries for sorting, such as java.util.Arrays and java.util.Collections. These libraries offer more efficient implementations of common sorting algorithms like quicksort, mergesort, and heapsort. Additionally, they provide utility methods to sort primitive types (e.g., int, long, double) and custom objects (e.g., arrays of custom classes).

Worked Example

Let's implement a simple merge sort function using the provided mergeSort() and merge() functions:

public class MergeSortExample {
public static void main(String[] args) {
int arr[] = {12, 11, 13, 5, 6, 7};
mergeSort(arr, 0, arr.length - 1);
for (int i = 0; i < arr.length; ++i) {
System.out.print(arr[i] + " ");
}
}

static void mergeSort(int arr[], int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}

static void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;

int L[] = new int[n1];
int R[] = new int[n2];

for (int i = 0; i < n1; ++i) {
L[i] = arr[left + i];
}
for (int j = 0; j < n2; ++j) {
R[j] = arr[mid + 1 + j];
}

int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k++] = L[i++];
} else {
arr[k++] = R[j++];
}
}

while (i < n1) {
arr[k++] = L[i++];
}

while (j < n2) {
arr[k++] = R[j++];
}
}
}

Common Mistakes

Not handling edge cases: Ensure your sorting algorithm can handle arrays with one or zero elements correctly. For example, bubble sort and selection sort must be modified to handle these cases appropriately.
Incorrect pivot selection: In quicksort, choosing a poor pivot can lead to inefficient sorting. Common strategies include selecting the first element, last element, or median-of-three.
Misunderstanding the time complexity: It's essential to understand the time complexity of each algorithm and choose the appropriate one based on the size and characteristics of your dataset. For example, bubble sort is inefficient for large datasets, while merge sort is more efficient but requires additional memory.
Ignoring built-in libraries: Using built-in libraries like java.util.Arrays or java.util.Collections can provide more efficient implementations of common sorting algorithms.
Not optimizing for stability: If you need to preserve the relative order of equal elements, use a stable sorting algorithm like merge sort or timsort.
Implementing inefficient versions of simple algorithms: Ensure that your implementation of bubble sort, selection sort, and insertion sort is optimized by using techniques like sentinel nodes or tail recursion to reduce the number of comparisons and swaps.
Not considering the impact of memory usage: Some sorting algorithms (e.g., merge sort) require additional memory for temporary arrays, which can be a concern when dealing with large datasets. Consider using in-place sorting algorithms or implementing custom data structures to reduce memory usage.
Ignoring parallelism opportunities: In modern computing environments, it's essential to consider parallelizing sorting algorithms to take advantage of multi-core processors. Implementing parallel versions of common sorting algorithms can significantly improve performance for large datasets.
Not testing with different data sets: Test your sorting algorithm with various input sizes and characteristics (e.g., sorted, reversed, random) to ensure it performs well in different scenarios.
Overcomplicating the solution: Sometimes, a simple algorithm like bubble sort or selection sort may be sufficient for small datasets or specific use cases. Don't always assume that a more complex algorithm is better; consider the trade-offs between time complexity, space complexity, and stability when choosing an algorithm.

Practice Questions

Implement bubble sort using a nested loop.
Write a recursive implementation of quicksort that selects the median-of-three as the pivot.
Given an unsorted array, write a function to find the index of the smallest element.
Implement insertion sort using two loops.
Compare the time complexity and efficiency of bubble sort, selection sort, insertion sort, merge sort, and quick sort for different input sizes.
Implement a parallel version of merge sort using Java's ForkJoinPool.
Write a custom sorting algorithm that sorts an array in ascending order using only comparisons (no swaps).
Analyze the time complexity and stability of the counting sort, radix sort, and bucket sort algorithms.
Implement a stable sorting algorithm using merge sort.
Write a function to sort a linked list using quicksort.

FAQ

What is the difference between stable and unstable sorting algorithms?

Stable sorting algorithms preserve the relative order of equal elements, while unstable sorting algorithms do not. Stable sorting algorithms are useful when you need to maintain the original order of certain data elements (e.g., when sorting records with identical keys).

Why are comparison-based sorting algorithms important