#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/fundamental-algorithms/divide-and-conquer/merge-sort-as-d-c

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/fundamental-algorithms/divide-and-conquer/merge-sort-as-d-c

Repovive

Merge Sort as D&C - Divide and Conquer | Fundamental Algorithms | Repovive

Repovive.

Fundamental Algorithms8 sections · 294 units2h total

Open in Course

Merge Sort as D&C

The canonical divide and conquer algorithm.

Merge sort is the textbook D&C example.

Divide: Split the array into two halves. Conquer: Recursively sort each half. Combine: Merge the two sorted halves.

function mergeSort(arr, left, right):
    if left >= right:
        return
    mid = (left + right) / 2
    mergeSort(arr, left, mid)
    mergeSort(arr, mid + 1, right)
    merge(arr, left, mid, right)

Why D&C works here: Merging two sorted arrays is $O(n)$ . Sorting each half is a smaller version of the same problem. The recurrence $T(n) = 2T(n/2) + O(n)$ gives $T(n) = O(n \log n)$ .