All Sorting Algorithms - Complete Guide with Visualizations

Sorting Algorithms Comparison

Algorithm	Best	Average	Worst	Space	Stable
Bubble Sort	`O(n)`	`O(n²)`	`O(n²)`	`O(1)`	✅ Yes
Selection Sort	`O(n²)`	`O(n²)`	`O(n²)`	`O(1)`	❌ No
Insertion Sort	`O(n)`	`O(n²)`	`O(n²)`	`O(1)`	✅ Yes
Merge Sort	`O(n log n)`	`O(n log n)`	`O(n log n)`	`O(n)`	✅ Yes
Quick Sort	`O(n log n)`	`O(n log n)`	`O(n²)`	`O(log n)`	❌ No
Heap Sort	`O(n log n)`	`O(n log n)`	`O(n log n)`	`O(1)`	❌ No
Counting Sort	`O(n+k)`	`O(n+k)`	`O(n+k)`	`O(k)`	✅ Yes
Radix Sort	`O(nk)`	`O(nk)`	`O(nk)`	`O(n+k)`	✅ Yes
Bucket Sort	`O(n+k)`	`O(n+k)`	`O(n²)`	`O(n)`	✅ Yes
Tim Sort	`O(n)`	`O(n log n)`	`O(n log n)`	`O(n)`	✅ Yes

When to use which?
• Small arrays (n < 50): Insertion Sort
• General purpose: Quick Sort or Merge Sort
• Stable sort needed: Merge Sort or Tim Sort
• Memory limited: Heap Sort or Quick Sort
• Integers in range: Counting Sort or Radix Sort

Bubble Sort

Bubble Sort repeatedly steps through the list, compares adjacent elements, and swaps them if they're in the wrong order. The largest elements "bubble up" to the end.

How It Works

Compare adjacent elements
Swap if they're in wrong order
Repeat until no swaps needed
After each pass, the largest unsorted element is in its correct position

Java

public static void bubbleSort(int[] arr) {
    int n = arr.length;
    boolean swapped;
    
    for (int i = 0; i < n - 1; i++) {
        swapped = false;
        
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // Swap arr[j] and arr[j+1]
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = true;
            }
        }
        
        // If no swapping occurred, array is sorted
        if (!swapped) break;
    }
}

// Time: O(n²) average, O(n) best (already sorted)
// Space: O(1)

Python

def bubble_sort(arr):
    n = len(arr)
    
    for i in range(n - 1):
        swapped = False
        
        for j in range(n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        
        if not swapped:
            break
    
    return arr

Selection Sort

Selection Sort divides the array into sorted and unsorted parts. It repeatedly finds the minimum element from the unsorted part and puts it at the beginning.

Java

public static void selectionSort(int[] arr) {
    int n = arr.length;
    
    for (int i = 0; i < n - 1; i++) {
        // Find minimum element in unsorted portion
        int minIdx = i;
        
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }
        
        // Swap minimum with first unsorted element
        int temp = arr[minIdx];
        arr[minIdx] = arr[i];
        arr[i] = temp;
    }
}

// Time: O(n²) - always
// Space: O(1)

Python

def selection_sort(arr):
    n = len(arr)
    
    for i in range(n - 1):
        min_idx = i
        
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    
    return arr

Insertion Sort

Insertion Sort builds the sorted array one element at a time by inserting each element into its correct position in the already sorted portion.

Best for: Small arrays, nearly sorted arrays, or as a sub-routine in hybrid algorithms like Tim Sort.

Java

public static void insertionSort(int[] arr) {
    int n = arr.length;
    
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        
        // Move elements greater than key one position ahead
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        
        arr[j + 1] = key;
    }
}

// Time: O(n²) average, O(n) best (already sorted)
// Space: O(1)

Python

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        
        arr[j + 1] = key
    
    return arr

Merge Sort

Merge Sort uses the divide-and-conquer approach. It divides the array into halves, sorts them recursively, then merges the sorted halves.

Algorithm Steps

Divide array into two halves
Recursively sort both halves
Merge the two sorted halves

Java

public static void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        
        // Sort first and second halves
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        
        // Merge the sorted halves
        merge(arr, left, mid, right);
    }
}

private static void merge(int[] arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    
    // Create temp arrays
    int[] L = new int[n1];
    int[] R = new int[n2];
    
    // Copy data to temp arrays
    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];
    
    // Merge temp arrays back
    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++];
        }
    }
    
    // Copy remaining elements
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

// Time: O(n log n) - always
// Space: O(n)

Python

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    result.extend(left[i:])
    result.extend(right[j:])
    return result

Quick Sort

Quick Sort picks a "pivot" element and partitions the array around it. Elements smaller than pivot go left, larger go right. This is done recursively.

Best Practice: Use randomized pivot or median-of-three to avoid O(n²) worst case on sorted arrays.

Java

public static 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);
    }
}

private static int partition(int[] arr, int low, int high) {
    int pivot = arr[high];  // Choose last element as pivot
    int i = low - 1;        // Index of smaller element
    
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            // Swap arr[i] and arr[j]
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    
    // Swap pivot to its correct position
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    
    return i + 1;
}

// Time: O(n log n) average, O(n²) worst
// Space: O(log n) - recursion stack

Python

def quick_sort(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)
        quick_sort(arr, low, pi - 1)
        quick_sort(arr, pi + 1, high)

def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    
    for j in range(low, high):
        if arr[j] < pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

Heap Sort

Heap Sort uses a binary heap data structure. It first builds a max-heap, then repeatedly extracts the maximum element and places it at the end.

Java

public static void heapSort(int[] arr) {
    int n = arr.length;
    
    // Build max heap
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
    
    // Extract elements from heap one by one
    for (int i = n - 1; i > 0; i--) {
        // Move current root to end
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        
        // Heapify the reduced heap
        heapify(arr, i, 0);
    }
}

private static void heapify(int[] arr, int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    
    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }
    
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }
    
    if (largest != i) {
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;
        
        heapify(arr, n, largest);
    }
}

// Time: O(n log n) - always
// Space: O(1)

Counting Sort

Counting Sort is a non-comparison sorting algorithm. It counts occurrences of each unique element and uses arithmetic to determine positions.

Best for: Integers within a known, limited range. Not suitable for large ranges or floating-point numbers.

Java

public static void countingSort(int[] arr) {
    int n = arr.length;
    
    // Find the range
    int max = Arrays.stream(arr).max().getAsInt();
    int min = Arrays.stream(arr).min().getAsInt();
    int range = max - min + 1;
    
    int[] count = new int[range];
    int[] output = new int[n];
    
    // Count occurrences
    for (int i = 0; i < n; i++) {
        count[arr[i] - min]++;
    }
    
    // Convert to cumulative count
    for (int i = 1; i < range; i++) {
        count[i] += count[i - 1];
    }
    
    // Build output array (traverse backwards for stability)
    for (int i = n - 1; i >= 0; i--) {
        output[count[arr[i] - min] - 1] = arr[i];
        count[arr[i] - min]--;
    }
    
    // Copy to original array
    System.arraycopy(output, 0, arr, 0, n);
}

// Time: O(n + k) where k is range
// Space: O(k)

Radix Sort

Radix Sort sorts numbers digit by digit, starting from the least significant digit (LSD) or most significant digit (MSD).

Java

public static void radixSort(int[] arr) {
    int max = Arrays.stream(arr).max().getAsInt();
    
    // Do counting sort for every digit
    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 each digit
    for (int i = 0; i < n; i++) {
        int digit = (arr[i] / exp) % 10;
        count[digit]++;
    }
    
    // Convert to 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]--;
    }
    
    System.arraycopy(output, 0, arr, 0, n);
}

// Time: O(d * (n + k)) where d = digits, k = base (10)
// Space: O(n + k)

Bucket Sort

Bucket Sort distributes elements into buckets, sorts each bucket individually (often using insertion sort), then concatenates them.

Java

public static void bucketSort(float[] arr) {
    int n = arr.length;
    if (n <= 0) return;
    
    // Create buckets
    ArrayList> buckets = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        buckets.add(new ArrayList<>());
    }
    
    // Put elements in buckets (assuming values are 0 to 1)
    for (int i = 0; i < n; i++) {
        int bucketIdx = (int) (arr[i] * n);
        buckets.get(bucketIdx).add(arr[i]);
    }
    
    // Sort individual buckets
    for (ArrayList bucket : buckets) {
        Collections.sort(bucket);
    }
    
    // Concatenate buckets
    int idx = 0;
    for (ArrayList bucket : buckets) {
        for (float val : bucket) {
            arr[idx++] = val;
        }
    }
}

// Time: O(n + k) average, O(n²) worst
// Space: O(n)

Shell Sort

Shell Sort is a generalized version of Insertion Sort. It allows exchange of far apart elements and gradually reduces the gap between elements to be compared.

Java

public static void shellSort(int[] arr) {
    int n = arr.length;
    
    // Start with big gap, then reduce
    for (int gap = n / 2; gap > 0; gap /= 2) {
        // Do insertion sort for this gap
        for (int i = gap; i < n; i++) {
            int temp = arr[i];
            int j = i;
            
            while (j >= gap && arr[j - gap] > temp) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            
            arr[j] = temp;
        }
    }
}

// Time: O(n log n) to O(n²) depending on gap sequence
// Space: O(1)

Tim Sort

Tim Sort is a hybrid sorting algorithm derived from Merge Sort and Insertion Sort. It's used by Python's sort() and Java's Arrays.sort() for objects.

Key Concepts

Run: A sequence of consecutive elements that are already sorted
Min Run: Minimum length for a run (typically 32-64)
Uses Insertion Sort for small runs
Merges runs using modified Merge Sort

Java (Simplified)

public static void timSort(int[] arr) {
    int n = arr.length;
    int MIN_RUN = 32;
    
    // Sort individual runs using insertion sort
    for (int i = 0; i < n; i += MIN_RUN) {
        insertionSort(arr, i, Math.min(i + MIN_RUN - 1, n - 1));
    }
    
    // Merge runs
    for (int size = MIN_RUN; size < n; size *= 2) {
        for (int left = 0; left < n; left += 2 * size) {
            int mid = left + size - 1;
            int right = Math.min(left + 2 * size - 1, n - 1);
            
            if (mid < right) {
                merge(arr, left, mid, right);
            }
        }
    }
}

private static void insertionSort(int[] arr, int left, int right) {
    for (int i = left + 1; i <= right; i++) {
        int temp = arr[i];
        int j = i - 1;
        
        while (j >= left && arr[j] > temp) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = temp;
    }
}

// Time: O(n log n), O(n) best case
// Space: O(n)

Why Tim Sort is popular:
• Stable sort (maintains relative order of equal elements)
• Excellent for partially sorted data (very common in real world)
• O(n) for already sorted data
• Used by Python, Java, Android, and Swift