Sorting Foundations

7 concept walkthroughs, each with a worked explanation and an interactive visualization, before you start solving problems in this area.

What is Sorting?

Sorting is the process of arranging items in a specific order: usually from smallest to largest (ascending) or largest to smallest (descending). Think of organizing books on a shelf by height, or arranging playing cards in your hand from lowest to highest.

• Sorting arranges elements in a specific ORDER
• Two main orders: ASCENDING (1,2,3...) or DESCENDING (9,8,7...)
• Sorted data enables FASTER searching (binary search)
• Different algorithms have different TRADE-OFFS
• Some algorithms work better for nearly-sorted data

Bubble Sort

Bubble Sort works by repeatedly stepping through the list, comparing adjacent elements, and swapping them if they're in the wrong order. The largest elements 'bubble up' to the end of the list, like air bubbles rising to the surface of water.

• Compare ADJACENT elements and swap if needed
• Largest elements 'BUBBLE UP' to the end
• Each pass guarantees ONE element is in place
• Simple but SLOW for large datasets
• Great for learning but rarely used in practice

for i from 0 to n-1:
    for j from 0 to n-i-1:
        if arr[j] > arr[j+1]:
            swap(arr[j], arr[j+1])

Selection Sort

Selection Sort divides the array into sorted and unsorted parts. It repeatedly finds the MINIMUM element from the unsorted part and moves it to the end of the sorted part. You're literally 'selecting' the smallest remaining element each time.

• Find the MINIMUM element in unsorted part
• SWAP it with the first unsorted element
• Sorted part GROWS from left to right
• Makes minimum number of SWAPS (O(n))
• Always O(n²) comparisons regardless of input

for i from 0 to n-1:
    minIndex = i
    for j from i+1 to n:
        if arr[j] < arr[minIndex]:
            minIndex = j
    swap(arr[i], arr[minIndex])

Insertion Sort

Insertion Sort builds the sorted array one element at a time. For each new element, it finds the correct position in the already-sorted part and INSERTS it there, shifting other elements as needed. Like sorting playing cards in your hand!

• Build sorted array ONE element at a time
• Take next element and INSERT into correct position
• SHIFT elements to make room for insertion
• Very efficient for NEARLY SORTED data
• Excellent for SMALL datasets and online sorting

for i from 1 to n-1:
    key = arr[i]
    j = i - 1
    while j >= 0 and arr[j] > key:
        arr[j+1] = arr[j]  // shift right
        j = j - 1
    arr[j+1] = key  // insert

Merge Sort

Merge Sort uses the 'Divide and Conquer' strategy. It divides the array into two halves, recursively sorts each half, and then MERGES the sorted halves back together. The magic happens in the merge step, combining two sorted arrays is very efficient!

• DIVIDE array into two halves
• CONQUER by recursively sorting each half
• MERGE the sorted halves together
• Guaranteed O(n log n) - always fast!
• Requires extra space for merging

mergeSort(arr, left, right):
    if left < right:
        mid = (left + right) / 2
        mergeSort(arr, left, mid)
        mergeSort(arr, mid+1, right)
        merge(arr, left, mid, right)

Quick Sort

Quick Sort also uses 'Divide and Conquer', but differently. It picks a PIVOT element and partitions the array so all smaller elements go left and larger go right. Then it recursively sorts the left and right parts. The partitioning is the key step!

• Pick a PIVOT element
• PARTITION: smaller elements left, larger right
• Pivot ends up in its FINAL position
• Recursively sort left and right partitions
• Fastest in practice for most cases

quickSort(arr, low, high):
    if low < high:
        pivotIndex = partition(arr, low, high)
        quickSort(arr, low, pivotIndex - 1)
        quickSort(arr, pivotIndex + 1, high)

partition(arr, low, high):
    pivot = arr[high]
    i = low - 1

    FOR j FROM low TO high - 1:
        IF arr[j] < pivot:
            i = i + 1
            swap arr[i] and arr[j]

    swap arr[i + 1] and arr[high]
    return i + 1

Which Sorting Algorithm to Use?

Each sorting algorithm has its strengths. For small arrays, simple algorithms like Insertion Sort work great. For large arrays, Merge Sort or Quick Sort are better. The 'best' algorithm depends on your data size, whether it's nearly sorted, and memory constraints.

• Small arrays (< 50): Insertion Sort is often fastest
• Large arrays: Quick Sort or Merge Sort
• Nearly sorted data: Insertion Sort shines
• Need guaranteed time: Merge Sort (always O(n log n))
• Memory matters: Quick Sort uses less space
• Stability needed: Merge Sort or Insertion Sort

All DSA learning paths