🔄 Different Sorting Algorithms Explained (Beginner to Advanced)

Sorting is one of the most important concepts in programming.
It helps in organizing data and is used in searching, databases, and many real-world applications.

In this blog, we will explore different sorting algorithms, their working, and their complexities.

📌 What is Sorting?

Sorting means arranging elements in a specific order:

Ascending → smallest to largest
Descending → largest to smallest

🔹 1. Bubble Sort

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

💻 Code:

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]
    return arr

⚡ Complexity:

Time: O(n²)
Space: O(1)

👉 Simple but inefficient for large data

🔹 2. Selection Sort

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

💻 Code:

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

⚡ Complexity:

Time: O(n²)
Space: O(1)

🔹 3. Insertion Sort

Builds the sorted array one element at a time.

💻 Code:

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

⚡ Complexity:

Time: O(n²)
Best Case: O(n)

👉 Efficient for small or nearly sorted data

🔹 4. Merge Sort

Uses divide and conquer:

Split array
Sort halves
Merge

💻 Code:

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

⚡ Complexity:

Time: O(n log n)
Space: O(n)

👉 Stable and efficient

🔹 5. Quick Sort

Picks a pivot and partitions the array.

💻 Code:

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

    pivot = arr[len(arr)//2]
    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)

⚡ Complexity:

Average: O(n log n)
Worst: O(n²)

👉 Very fast in practice

🔹 6. Heap Sort

Uses a heap data structure to sort elements.

💻 Code:

import heapq

def heap_sort(arr):
    heapq.heapify(arr)
    return [heapq.heappop(arr) for _ in range(len(arr))]

⚡ Complexity:

Time: O(n log n)
Space: O(1) (in-place version)

📊 Comparison Table

Algorithm Time Complexity Space Stable
Bubble Sort O(n²) O(1) Yes
Selection Sort O(n²) O(1) No
Insertion Sort O(n²) O(1) Yes
Merge Sort O(n log n) O(n) Yes
Quick Sort O(n log n)* O(log n) No
Heap Sort O(n log n) O(1) No

🧠 Key Takeaways