Efficient Sorting Algorithms

While simple sorts (bubble, selection, insertion) are O(n²), efficient algorithms achieve O(n log n) using divide-and-conquer or heap structures.

Merge Sort

Merge sort divides the array in half, recursively sorts each half, then merges the sorted halves.

Merge Sort Algorithm

1. Divide array into two halves
2. Recursively sort each half
3. Merge two sorted halves

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

Time Complexity: O(n log n) - all cases
Space Complexity: O(n) - extra arrays for merging
Stable: Yes (maintains relative order)

Quick Sort

Quick sort picks a pivot, partitions array around it, then recursively sorts partitions.

Quick Sort Algorithm

1. Choose a pivot element
2. Partition: elements < pivot go left, >= pivot go right
3. Recursively quick sort left and right

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)

Time Complexity:

• Average: O(n log n)
• Worst: O(n²) - when pivot is always smallest/largest

Space Complexity: O(log n) for recursion
Stable: No (standard implementation)

Heap Sort

Heap sort builds a max heap, then repeatedly extracts the maximum element.

Heap Sort Algorithm

1. Build max heap from array
2. Swap root (max) with last element
3. Reduce heap size and heapify root
4. Repeat until heap size = 1

def heap_sort(arr):
    n = len(arr)
    
    # Build max heap
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    
    # Extract elements one by one
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]  # Swap
        heapify(arr, i, 0)
    
    return arr

def heapify(arr, n, i):
    """Maintain max heap property."""
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2
    
    if left < n and arr[left] > arr[largest]:
        largest = left
    
    if right < n and arr[right] > arr[largest]:
        largest = right
    
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

Time Complexity: O(n log n) - all cases
Space Complexity: O(1) - sorts in place
Stable: No

Sorting Algorithm Comparison

When to Use Each Sorting Algorithm

Merge Sort:

• Need guaranteed O(n log n)
• Need stable sort
• Have extra memory available
• Linked lists (efficient)

Quick Sort:

• Average case performance critical
• Space is limited
• Data is random (not already sorted)
• Most common choice in practice

Heap Sort:

• Need O(n log n) worst case
• No extra memory available
• Don't need stability

Quiz

Key Takeaways

✅ Merge sort: Guaranteed O(n log n), stable, uses O(n) space
✅ Quick sort: Average O(n log n), in-place, most popular
✅ Heap sort: Worst-case O(n log n), O(1) space, not stable
✅ All beat O(n²) simple sorts for large datasets
✅ Choose based on: stability needs, space constraints, data patterns

Master efficient sorting for handling large-scale data! 🚀