Merge Sort

Merge sort is a divide and conquer algorithm that sorts an array.

With merge sort, the input array is split into multiple subproblems.

Each subproblem is then merged into the result array.

For example, let's say you're given the following array of numbers.

arr = [3, 1, 5, 2, 9, 8]

The image below shows the steps that the array is sorted.

Try it

Before you look at the solution, try to code it yourself.

def merge_sort(arr: list[int]) -> list[int]:
    # implement merge_sort
    return arr

1def merge_sort(arr: list[int]) -> list[int]:
2    # implement merge_sort
3    return arr
4

It takes logarithmic time to divide the problem into subprobems.

Merging the sorted sub arrays into the output takes linear time.

Therefore, the overall time complexity of the merge sort is O(n*log n).

Master Sorting & Searching by trying the coding challenges below.

Stack Bash helps new and veteran software engineers master data structures and algorithms for technical interviews.