Comprehensive Overview of Common Sorting Algorithms with Java Implementations

Bubble Sort

Bubble Sort repeatedly swaps adjacent out‑of‑order elements until the array is sorted; its average time complexity is O(n²) and it is stable.

public static void BubbleSort(int[] arr) { /* implementation */ }

Algorithm Steps

1. Compare adjacent elements and swap if needed. 2. After each pass, the largest element bubbles to the end. 3. Repeat until no swaps are required.

Optimization

A flag can stop early when a pass makes no swaps.

Selection Sort

Selection Sort repeatedly selects the minimum (or maximum) element from the unsorted portion and moves it to the sorted portion; time complexity O(n²), not stable.

public static void select_sort(int[] array, int length) { /* implementation */ }

Insertion Sort

Insertion Sort builds a sorted array one element at a time by inserting each new element into its proper position; time complexity O(n²), stable.

public static void insert_sort(int[] array, int length) { /* implementation */ }

Shell Sort

Shell Sort is an improved version of insertion sort that uses a decreasing gap sequence to partially sort the array, reducing overall complexity.

public static void shell_sort(int[] array, int length) { /* implementation */ }

Merge Sort

Merge Sort is a divide‑and‑conquer algorithm that recursively splits the array and merges sorted sub‑arrays; time complexity O(n log n), stable, requires extra memory.

void MemeryArray(int[] a, int n, int[] b, int m, int[] c) { /* implementation */ }

Quick Sort

Quick Sort selects a pivot and partitions the array into elements less than and greater than the pivot, then recursively sorts the partitions; average time O(n log n), worst‑case O(n²), not stable.

public static void quickSort(int[] a, int l, int r) { /* implementation */ }

Heap Sort

Heap Sort builds a binary heap (max‑heap or min‑heap) and repeatedly extracts the root to produce a sorted array; time complexity O(n log n), not stable.

public static void MakeMinHeap(int[] a, int n) { /* implementation */ }

Counting Sort

Counting Sort counts occurrences of each distinct value and computes positions; linear time O(n + k) for integer keys within a known range, stable but uses extra space.

public static void countingSort(int[] array, int range) throws Exception { /* implementation */ }

Bucket Sort

Bucket Sort distributes elements into a number of buckets based on a mapping function and sorts each bucket individually; performance depends on uniform distribution.

public void sort(Double[] a) { /* implementation */ }

Radix Sort

Radix Sort processes integer keys digit by digit using counting sort as a sub‑routine; works for integers and strings, stable, time O(n·k) where k is number of digits.

public int[] sort(int[] sourceArray) throws Exception { /* implementation */ }