Combine: $[10, 30, 40, 50, 70, 80, 90]$

Merge Sort

Concept: A divide-and-conquer algorithm. It divides the unsorted list into $n$ sublists, each containing one element, and repeatedly merges sublists to produce new sorted sublists until there is only one sorted list.

Algorithm:

function mergeSort(array):
    if length(array) <= 1:
        return array

    mid = length(array) / 2
    left = array[0...mid-1]
    right = array[mid...length(array)-1]

    left = mergeSort(left)
    right = mergeSort(right)

    return merge(left, right)

function merge(left, right):
    result = []
    i = 0, j = 0
    while i < length(left) and j < length(right):
        if left[i] <= right[j]:
            add left[i] to result
            i = i + 1
        else:
            add right[j] to result
            j = j + 1
    add remaining elements from left to result
    add remaining elements from right to result
    return result

Example: Sorting $[38, 27, 43, 3, 9, 82, 10]$
1. Divide:
  - $[38, 27, 43, 3]$ and $[9, 82, 10]$
  - Then further into single elements
2. Merge:
  - $[27, 38]$, $[3, 43]$ -> $[3, 27, 38, 43]$
  - $[9, 82]$, $[10]$ -> $[9, 10, 82]$
  - Finally merge $[3, 27, 38, 43]$ and $[9, 10, 82]$
3. Result: $[3, 9, 10, 27, 38, 43, 82]$

Heap Sort

Concept: A comparison-based sorting technique based on the Binary Heap data structure. It's similar to selection sort where we first find the maximum element and place it at the end.

Algorithm:

function heapSort(array):
    n = length(array)

    // Build max heap
    for i from n/2 - 1 down to 0:
        heapify(array, n, i)

    // Extract elements one by one
    for i from n-1 down to 0:
        swap(array[0], array[i]) // Move current root to end
        heapify(array, i, 0) // Call max heapify on reduced heap

function heapify(array, n, i):
    largest = i // Initialize largest as root
    left = 2 * i + 1
    right = 2 * i + 2

    // If left child is larger than root
    if left < n and array[left] > array[largest]:
        largest = left

    // If right child is larger than largest so far
    if right < n and array[right] > array[largest]:
        largest = right

    // If largest is not root
    if largest != i:
        swap(array[i], array[largest])
        heapify(array, n, largest)

Example: Sorting $[4, 10, 3, 5, 1]$
1. Build Max Heap:
  - Initial: $[4, 10, 3, 5, 1]$
  - Heapify from last non-leaf node (index 1, value 10): $[4, 10, 3, 5, 1]$ becomes $[10, 5, 3, 4, 1]$ (after some swaps)
2. Extract Max:
  - Swap 10 (root) with 1 (last): $[1, 5, 3, 4, \underline{10}]$
  - Heapify remaining 4 elements: $[5, 4, 3, 1, \underline{10}]$
  - Swap 5 (root) with 1 (last of heap): $[1, 4, 3, \underline{5}, \underline{10}]$
  - Heapify remaining 3 elements: $[4, 3, 1, \underline{5}, \underline{10}]$
  - Continue until sorted: $[1, 3, 4, 5, 10]$

28:["$","main",null,{"className":"pt-[57px]","children":["$","div",null,{"className":"max-w-7xl mx-auto px-4 sm:px-6 py-6","children":[["$","nav",null,{"aria-label":"Breadcrumb","className":"mb-4","children":["$","ol",null,{"className":"flex items-center gap-1 text-sm text-muted-foreground","children":[["$","li",null,{"children":[