Sorting Algorithms Visualized

Sorting algorithms are fundamental building blocks in computer science. They organize data into a specific order, which is essential for efficient searching, data analysis, and countless real-world applications from database indexing to e-commerce product listings.

Why Sorting Matters

Consider a database with 10 million user records. Using an inefficient $O(n^2)$ algorithm could take hours to sort, while an optimized $O(n log n)$ algorithm completes in seconds. This isn't just academic—it's the difference between a responsive application and a frustrated user.

Comparison-Based Sorting Algorithms

All algorithms below work by comparing pairs of elements to determine their relative order.

Bubble Sort

Bubble Sort is the simplest sorting algorithm, often taught as an introduction to the concept. It works by repeatedly stepping through the list, comparing adjacent elements, and swapping them if they're in the wrong order.

How it works:

1. Start at the beginning of the array
2. Compare each pair of adjacent elements
3. Swap them if they're in the wrong order
4. Repeat until no swaps are needed

Bubble Sort is rarely used in practice due to its poor performance, but it's valuable for understanding sorting concepts.

Selection Sort

Selection Sort improves on Bubble Sort by reducing the number of swaps. It divides the array into sorted and unsorted regions, repeatedly finding the minimum element from the unsorted region and moving it to the end of the sorted region.

How it works:

1. Find the minimum element in the unsorted portion
2. Swap it with the first unsorted element
3. Move the boundary between sorted/unsorted one position right
4. Repeat until the entire array is sorted

Insertion Sort

Insertion Sort builds the final sorted array one element at a time. It's similar to how you might sort playing cards in your hand—taking each new card and inserting it into its correct position among the already-sorted cards.

How it works:

1. Start with the second element (first is "sorted")
2. Compare it with elements to its left
3. Shift larger elements right to make space
4. Insert the element in its correct position
5. Repeat for all remaining elements

Divide-and-Conquer Algorithms

These algorithms break the problem into smaller subproblems, solve them recursively, and combine the results.

Quick Sort

Quick Sort is one of the most widely used sorting algorithms. It works by selecting a "pivot" element and partitioning the array so that elements smaller than the pivot come before it, and larger elements come after.

How it works:

1. Choose a pivot element (often the last or random element)
2. Partition: rearrange so elements < pivot are left, > pivot are right
3. Recursively apply Quick Sort to the left and right subarrays
4. The array is sorted when all subarrays have 0 or 1 elements

Merge Sort

Merge Sort guarantees $O(n log n)$ performance by dividing the array in half, recursively sorting each half, then merging the sorted halves back together.

How it works:

1. Divide the array into two halves
2. Recursively sort each half
3. Merge the two sorted halves into one sorted array
4. Base case: arrays of size 0 or 1 are already sorted

Merge Sort is often preferred when stability is required or when sorting linked lists (where the space overhead is minimal).

Algorithm Comparison

Code Examples

Bubble Sort

void bubbleSort(int arr[], int n) {
    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], arr[j + 1]);
            }
        }
    }
}

Selection Sort

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }
        swap(arr[i], arr[minIdx]);
    }
}

Insertion Sort

void insertionSort(int arr[], int n) {
    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;
    }
}

Quick Sort

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

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

Merge Sort

void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1, n2 = right - mid;
    int L[n1], R[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) {
        arr[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];
    }
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

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

Try It Yourself

Use the interactive visualizer below to see how each algorithm works step by step. Experiment with different array sizes and speeds to observe how the algorithms behave!