Merge Sort, Quick Sort, Heap Sort

카테고리

Algorithm and DataStructure

Index

Sorting Algorithm

MergeSort

QuickSort

HeapSort

날짜

2025/01/20

1. Merge Sort

Merge sort is a divide-and-conquer algorithm that splits an array into smaller subarrays, sorts each subarray, and then merges them back together in sorted order.

Steps are

Divide: Recursively split the array into two halves until each subarray contains a single element or is empty.

Conquer: Merge the two sorted halves in to a singe sorted Array

Combine: Continue merging sorted subarrays up to recursive call stack 

def merge(left, right):
    sorted_array = []
    i = j = 0

    # Step 3: Compare elements from both halves and build the sorted array
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            sorted_array.append(left[i])
            i += 1
        else:
            sorted_array.append(right[j])
            j += 1

    # Step 4: Append any remaining elements from both halves
    sorted_array.extend(left[i:])
    sorted_array.extend(right[j:])

    return sorted_array
 
 def merge_sort(arr):
    # Base case: An array with 0 or 1 element is already sorted
    if len(arr) <= 1:
        return arr

    # Step 1: Split the array into two halves - O(logn)
    mid = len(arr) // 2
    left_half = merge_sort(arr[:mid])
    right_half = merge_sort(arr[mid:])

    # Step 2: Merge the sorted halves - O(n)
    return merge(left_half, right_half)

# Example usage
arr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = merge_sort(arr)
print("Sorted array:", sorted_arr)
Python
복사

Time complexity of merge sort is

O(nlogn)

•

Divide step : Since the algorithm divides the array into two halves recursively, it creates lognlog nlogn levels of division.

→ each level requires splitting the array in half; independent of the input’s initial order

•

Merge step: At each level, the algorithm merges the subarray, and to total merging cost is O(n)

2. Quick Sort

Quick sort is a divide-and-conquer algorithm that partitions an array around a pivot element, ensuring that:

•

All elements smaller than the pivot are on left

•

All elements greater than the pivot are on right.

→ This process is repeated recursively on the left and right partition.

Steps

Choose a pivot 

Partitioning : Rearrange the array so that elements smaller thatn the pivot place left of the pivot and the elements larger are on the right. 

Recursion : Apply the same process to the subarrays on the left and right of the pivot.

def quick_sort(arr):
    # Base case: Arrays with 0 or 1 elements are already sorted
    if len(arr) <= 1:
        return arr
    
    # Step 1: Choose a pivot (last element in this case)
    pivot = arr[-1]
    left = [x for x in arr[:-1] if x <= pivot]  # O(n)
    right = [x for x in arr[:-1] if x > pivot]  # O(n)

    # Step 2: Recursively sort the left and right partitions, then combine
    return quick_sort(left) + [pivot] + quick_sort(right)

# Example Usage
arr = [10, 80, 30, 90, 40, 50, 70]
sorted_arr = quick_sort(arr)
print("Sorted array (Quick Sort):", sorted_arr)
Python
복사

Time complexity

Partitioning - O(n)O(n)O(n)

Recursive Sorting 

•

if size of the left and right partition are k and n-1-k,

◦

Sorting left : T(K)T(K)T(K)

◦

Sorting right: T(n−k−1) T(n-k-1)T(n−k−1)

•

T(n)=T(k)+T(n−k−1)+O(n)=O(n)T(n) = T(k) + T(n-k-1) + O(n) = O(n)T(n)=T(k)+T(n−k−1)+O(n)=O(n)

•

Best and Average Cases: O(nlogn)O(nlogn)O(nlogn); when on good pivot choices, with arrays splitted evenly

◦

The pivot divides the array into two roughly equal halves; k=n/2k = n/2k=n/2

◦

Recurrence becomes  T(n)=2T(n/2)+O(n)T(n) = 2T(n/2) + O(n)T(n)=2T(n/2)+O(n)

◦

T(n)=O(nlogn)T(n) = O(nlogn)T(n)=O(nlogn)

•

Worst Cases: O(n2)O(n^2)O(n2) ; poor pivot choices create unbalanced partitions 

◦

if pivot is the smallest or largest element, it creates one partition of size n−1n-1n−1 and the other of size 000

◦

T(n)=T(n−1)+O(n)T(n) = T(n-1) + O(n)T(n)=T(n−1)+O(n)

◦

T(n)=O(n2)T(n) = O(n^2)T(n)=O(n2)

3. Heap Sort

Heap Sort uses a binary heap data structure to sort an array.

A binary heap is a complete binary tree with:

•

Max-Heap : The root node is largest element, and every parent node is greater than or equal to its children.

•

Heap Sort transforms the input array into a max-heap and then repeatedly extracts the largest element to build the sorted array.

Step

Heapify: Convert the array into max-heap.

Extract Elements : Remove the root and  place it at the end of the array, then reheapify the remaining elements. 

Repeat until the heap is empty.

def heapify(arr, n, i):
    largest = i  # Initialize the largest as root
    left = 2 * i + 1  # Left child index
    right = 2 * i + 2  # Right child index

    # Check if the left child exists and is greater than the root
    if left < n and arr[left] > arr[largest]:
        largest = left

    # Check if the right child exists and is greater than the largest
    if right < n and arr[right] > arr[largest]:
        largest = right

    # If the largest is not the root, swap and continue heapifying
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heap_sort(arr):
    n = len(arr)

    # Step 1: Build a max-heap
    # Start from the last non-leaf node
    for i in range(n // 2 - 1, -1, -1):  
        heapify(arr, n, i)

    # Step 2: Extract elements from the heap
    # Swap the root with the last element
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]  
        heapify(arr, i, 0)  # Reheapify the reduced heap

# Example Usage
arr = [4, 10, 3, 5, 1]
heap_sort(arr)
print("Sorted array (Heap Sort):", arr)
Python
복사

Time Complexity

•

Best, Average, Worst Case : O(nlogn)O(nlogn)O(nlogn)

◦

Heapifying - lognlognlogn for each element nnn