AlgoView

Merge Sort

Speed

About algorithm

Explanation

Merge Sort is a divide-and-conquer algorithm that recursively splits the array into halves, sorts each half, and then merges the sorted halves to produce a sorted array.

Steps

  1. Divide the array into two halves.
  2. Recursively sort each half.
  3. Merge the two sorted halves into one sorted array.
  4. Repeat until the entire array is sorted.

Pseudocode

mergeSort(arr):
  if len(arr) <= 1:
    return arr
  mid = len(arr) / 2
  left = mergeSort(arr[:mid])
  right = mergeSort(arr[mid:])
  return merge(left, right)

Complexity

Time: O(n log(n))

Space: O(n)