Stack Bash - Master data structures and algorithms

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.
Merge sort algorithm

Try it

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


Time Complexity

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).

5 Essential Sorting & Searching Coding Interview Problems

Master Sorting & Searching by trying the coding challenges below.
  1. 1.Merge intervalsMedium
  2. 2.Kth largest in arrayMedium
  3. 3.Intersection of ArraysMedium
  4. 4.Search sorted matrixHard
  5. 5.Search row & col sorted matrixHard

Want to confidently pass your next coding interview?

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