DSA Sorting

Sorting is the process of arranging elements in a specific order — typically ascending or descending. Sorted data enables faster operations like binary search, simplifies comparisons, and is required by many algorithms. Sorting is a foundational topic in DSA, and understanding different sorting algorithms teaches key concepts like time-space trade-offs, recursion, and divide-and-conquer.

Bubble Sort

Bubble sort is the simplest sorting algorithm. It repeatedly steps through the list and compares adjacent elements, swapping them if they are in the wrong order. Larger elements "bubble up" toward the end of the list with each pass.

How It Works

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]   # Swap
    return arr

print(bubble_sort([64, 34, 25, 12, 22]))
# Output: [12, 22, 25, 34, 64]

• Time Complexity: O(n²) worst and average case.
• Space: O(1) — sorts in place.
• Best for: Learning purposes, very small datasets.

Selection Sort

Selection sort divides the list into a sorted and unsorted portion. In each pass, it finds the minimum element in the unsorted portion and swaps it to the front of that portion.

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        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]   # Swap minimum to front
    return arr

print(selection_sort([29, 10, 14, 37, 13]))
# Output: [10, 13, 14, 29, 37]

• Time Complexity: O(n²) in all cases.
• Space: O(1) — in place.
• Advantage: Minimizes swaps — useful when writes are expensive.

Insertion Sort

Insertion sort builds the sorted list one element at a time. For each new element, it finds its correct position within the already-sorted portion and inserts it there — like sorting playing cards in a hand.

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        # Shift elements greater than key one position ahead
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

print(insertion_sort([5, 2, 4, 6, 1, 3]))
# Output: [1, 2, 3, 4, 5, 6]

• Time Complexity: O(n²) worst case; O(n) best case (already sorted).
• Space: O(1) — in place.
• Best for: Nearly sorted data; small arrays.

Merge Sort

Merge sort is a divide-and-conquer algorithm. It recursively splits the array in half until each sub-array has one element, then merges the sub-arrays back together in sorted order. It is stable and efficient for large datasets.

How It Works

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = merge_sort(arr[:mid])    # Sort left half
    right = merge_sort(arr[mid:])   # Sort right half
    return merge(left, right)       # Merge the two halves

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

print(merge_sort([38, 27, 43, 3, 9, 82, 10]))
# Output: [3, 9, 10, 27, 38, 43, 82]

• Time Complexity: O(n log n) in all cases.
• Space: O(n) — requires extra memory.
• Best for: Large datasets, linked lists, stable sorting.

Quick Sort

Quick sort is another divide-and-conquer algorithm. It selects a pivot element and partitions the array into two parts: elements smaller than the pivot and elements larger than the pivot. It then recursively sorts both parts.

def quick_sort(arr):
    if len(arr) <= 1:
        return arr

    pivot = arr[len(arr) // 2]   # Choose middle element as pivot
    left   = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right  = [x for x in arr if x > pivot]

    return quick_sort(left) + middle + quick_sort(right)

print(quick_sort([3, 6, 8, 10, 1, 2, 1]))
# Output: [1, 1, 2, 3, 6, 8, 10]

• Time Complexity: O(n log n) average; O(n²) worst case (bad pivot).
• Space: O(log n) for recursive stack.
• Best for: General-purpose sorting, in-memory sorting of large arrays.

Built-in Sorting in Python

Python's built-in sorting uses Timsort — a hybrid of merge sort and insertion sort. It achieves O(n log n) in the worst case and is highly optimized.

# sort() — sorts the list in place
numbers = [5, 2, 8, 1, 9]
numbers.sort()
print(numbers)          # Output: [1, 2, 5, 8, 9]

# sorted() — returns a new sorted list
original = [5, 2, 8, 1, 9]
new_list = sorted(original)
print(original)         # Output: [5, 2, 8, 1, 9] — unchanged
print(new_list)         # Output: [1, 2, 5, 8, 9]

# Sort in descending order
print(sorted(original, reverse=True))   # Output: [9, 8, 5, 2, 1]

# Sort by custom key (e.g., string length)
words = ["banana", "fig", "apple", "kiwi"]
print(sorted(words, key=len))   # Output: ['fig', 'kiwi', 'apple', 'banana']

Sorting Algorithm Comparison

• Bubble Sort: O(n²) | Simple | Only for learning
• Selection Sort: O(n²) | Minimal swaps | Small datasets
• Insertion Sort: O(n²) / O(n) best | Good for nearly sorted data
• Merge Sort: O(n log n) | Stable | Large datasets, linked lists
• Quick Sort: O(n log n) avg | In-place | General purpose, fast in practice
• Python's sort(): O(n log n) | Timsort | Best choice for Python

Key Points

• Sorting organizes data, enabling faster algorithms like binary search.
• Bubble, selection, and insertion sort are O(n²) — suitable only for small or nearly sorted data.
• Merge sort and quick sort are O(n log n) — efficient for large datasets.
• Merge sort guarantees O(n log n) always; quick sort can degrade to O(n²) with poor pivot selection.
• Python's built-in sort() and sorted() use Timsort — the most practical choice for Python programs.
• Understanding sorting algorithms deeply reveals fundamental algorithmic patterns like divide-and-conquer.