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

$ curl repovive.com/roadmaps/fundamental-algorithms/sorting-algorithms/merge-sort-code

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

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

$ curl repovive.com/roadmaps/fundamental-algorithms/sorting-algorithms/merge-sort-code

Repovive

Merge Sort - Code - Sorting Algorithms | Fundamental Algorithms | Repovive

Repovive.

Fundamental Algorithms8 sections · 294 units2h total

Open in Course

Merge Sort - Code

Implementation and analysis.

Here is the implementation of merge sort:

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)

function merge(arr, left, mid, right):
    create temp arrays L and R
    copy arr[left..mid] to L
    copy arr[mid+1..right] to R
    merge L and R back into arr[left..right]

Time: $O(n \log n)$ always. Each level of recursion does $O(n)$ work. There are $\log n$ levels.

Space: $O(n)$ for the temporary arrays during merge (excluding input array).

Stability: Stable. When equal elements compare, take from the left array first.