CA 17 - Different Sorting Methods

Introduction

Sorting is one of the most fundamental concepts in programming. It helps organize data in a specific order (ascending or descending), making it easier to search, analyze, and process.

In this blog, I will explain four important sorting algorithms:

Bubble Sort
Insertion Sort
Selection Sort
Merge Sort

Bubble Sort

Idea

Bubble Sort repeatedly compares adjacent elements and swaps them if they are in the wrong order.

How it Works

Compare two adjacent elements
Swap if needed
Repeat this for the entire array
After each pass, the largest element moves to the end

Code (Python)

a = [5, 3, 8, 4]

n = len(a)

for i in range(n):
    for j in range(0, n - i - 1):
        if a[j] > a[j + 1]:
            a[j], a[j + 1] = a[j + 1], a[j]

print(a)

Use When:

You are learning sorting basics
→ Helps understand comparisons, swaps, and iteration
Dataset is extremely small (like < 10 elements)
→ Overhead of complex algorithms is unnecessary
You need to detect if an array is already sorted
→ Optimized Bubble Sort can stop early if no swaps happen
Educational visualization
→ Very intuitive to visualize step-by-step

Avoid When:

Dataset is large
Performance matters

Insertion Sort

Idea

Build the sorted array one element at a time by inserting elements into their correct position.

How it Works

Take one element
Compare with previous elements
Shift elements to make space
Insert at correct position

Code (Python)

a = [5, 3, 8, 4]

for i in range(1, len(a)):
    k = a[i]
    j = i - 1

    while j >= 0 and a[j] > k:
        a[j + 1] = a[j]
        j -= 1

    a[j + 1] = k

print(a)

Use When:

Array is already or nearly sorted
→ Time complexity becomes close to O(n)
You are processing data one-by-one (streaming data)
→ You can insert elements in correct position dynamically
Small datasets (like < 50 elements)
→ Very low overhead compared to complex algorithms
Used inside advanced algorithms
→ Hybrid algorithms (like TimSort) use it for small partitions

Avoid When:

Data is large and random
Worst-case performance matters

Selection Sort

Idea

Select the smallest element and place it at the correct position.

How it Works

Find minimum element
Swap it with first element
Repeat for remaining array

Code (Python)

a = [5, 3, 8, 4]

n = len(a)

for i in range(n):
    m = i
    for j in range(i + 1, n):
        if a[j] < a[m]:
            m = j
    a[i], a[m] = a[m], a[i]

print(a)

Use When:

Number of swaps must be minimized
→ It performs only O(n) swaps
Memory writes are costly (e.g., flash memory)
→ Fewer swaps = less wear
Very small datasets
Simplicity is preferred over performance

Avoid When:

Large datasets
Time efficiency is important

Merge Sort

Idea

Divide the array into smaller parts, sort them, and then merge them back.

How it Works

Divide array into halves
Recursively sort both halves
Merge sorted halves

Code (Python)

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

    m = len(a) // 2
    l = merge_sort(a[:m])
    r = merge_sort(a[m:])

    return merge(l, r)

def merge(l, r):
    res = []
    i = j = 0

    while i < len(l) and j < len(r):
        if l[i] < r[j]:
            res.append(l[i])
            i += 1
        else:
            res.append(r[j])
            j += 1

    res.extend(l[i:])
    res.extend(r[j:])
    return res

a = [5, 3, 8, 4]
print(merge_sort(a))

Use When:

Large datasets
→ Guaranteed O(n log n) performance
Stable sorting is required
→ Maintains order of equal elements
Linked Lists
→ Works very efficiently without random access
External sorting (data too large for memory)
→ Used in databases and file systems
Parallel processing
→ Can be divided and processed independently

Avoid When:

Memory is very limited (uses extra space)
Simpler algorithms are sufficient