Implementation

Let’s code merge sort. It’s elegant with recursion.

Complete Implementation


              function mergeSort(arr) {
// Base case
if (arr.length <= 1) {
  return arr;
}

// Divide
const mid = Math.floor(arr.length / 2);
const left = mergeSort(arr.slice(0, mid));
const right = mergeSort(arr.slice(mid));

// Conquer (merge)
return merge(left, right);
}

function merge(left, right) {
const result = [];
let i = 0, j = 0;

while (i < left.length && j < right.length) {
  if (left[i] <= right[j]) {
    result.push(left[i]);
    i++;
  } else {
    result.push(right[j]);
    j++;
  }
}

return result.concat(left.slice(i)).concat(right.slice(j));
}


              def merge_sort(arr):
  # Base case
  if len(arr) <= 1:
      return arr
  
  # Divide
  mid = len(arr) // 2
  left = merge_sort(arr[:mid])
  right = merge_sort(arr[mid:])
  
  # Conquer (merge)
  return merge(left, right)

def merge(left, right):
  result = []
  i = j = 0
  
  while i < len(left) and j < len(right):
      if left[i] <= right[j]:
          result.append(left[i])
          i += 1
      else:
          result.append(right[j])
          j += 1
  
  return result + left[i:] + right[j:]

Try It Yourself

🟨 JavaScript Merge Sort Implementation

📟 Console Output

Run code to see output...

Code Explanation

Base case: Array with 0 or 1 element is already sorted
Divide: Split array into two halves
Recurse: Sort each half recursively
Merge: Combine sorted halves using merge function

Edge Cases

Empty array: Returns empty array (base case)
Single element: Returns as-is (base case)
Already sorted: Still divides and merges (but merge is efficient)

What’s Next?

Now that you can implement it, let’s analyze its performance and complexity.

Progress 71%

Page 5 of 7

← Previous → Next

Sign In