FixCode

Fix the Merge Sort Implementation

Medium

Challenge 15 of 20

Fix the Merge Sort Implementation

Medium

This implementation of Merge Sort has a bug that causes it to produce incorrect results for certain inputs. Find and fix the issue.

Challenge 15 of 20

50 XP

Community Solutions

AlgorithmsSortingArraysJavaScript

Exit Challenge

Test Cases

0/3 passing

Test Case #1

Input: mergeSort([5, 3, 8, 4, 2])

Expected: [2, 3, 4, 5, 8]

Run tests to see results

Test Case #2

Input: mergeSort([1, 1, 1, 1])

Expected: [1, 1, 1, 1]

Run tests to see results

Test Case #3

Input: mergeSort([9, 8, 7, 6, 5, 4, 3, 2, 1])

Expected: [1, 2, 3, 4, 5, 6, 7, 8, 9]

Run tests to see results

solution.js

<span class="token keyword">function</span> mergeSort(arr) {
  <span class="token keyword">if</span> (arr.length <;= <span <span class="token keyword">class</span>="token number">1</span>) {
    <span class="token keyword">return</span> arr;
  }
  
  <span class="token keyword">const</span> middle = Math.floor(arr.length / <span <span class="token keyword">class</span>="token number">2</span>);
  <span class="token keyword">const</span> left = arr.slice(<span <span class="token keyword">class</span>="token number">0</span>, middle);
  <span class="token keyword">const</span> right = arr.slice(middle);
  
  <span class="token keyword">return</span> merge(mergeSort(left), mergeSort(right));
}

<span class="token keyword">function</span> merge(left, right) {
  <span class="token keyword">let</span> result = [];
  <span class="token keyword">let</span> leftIndex = <span <span class="token keyword">class</span>="token number">0</span>;
  <span class="token keyword">let</span> rightIndex = <span <span class="token keyword">class</span>="token number">0</span>;
  
  <span class="token keyword">while</span> (leftIndex <; left.length &;&; rightIndex <; right.length) {
    <span class="token keyword">if</span> (left[leftIndex] <; right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex++;  {
    <span class="token keyword">if</span> (left[leftIndex] <; right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex++;
    } <span class="token keyword">else</span> {
      result.push(right[rightIndex]);
      rightIndex++;
    }
  }
  
  <span <span class="token keyword">class</span>=<span <span class="token keyword">class</span>="token string">"token comment"</span>>// We need to concatenate the remaining elements</span>
  <span <span class="token keyword">class</span>=<span <span class="token keyword">class</span>="token string">"token comment"</span>>// This is where the bug is - we&#<span <span class="token keyword">class</span>="token number">039</span>;re not adding remaining elements</span>
  <span class="token keyword">return</span> result;
}

function mergeSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }
  
  const middle = Math.floor(arr.length / 2);
  const left = arr.slice(0, middle);
  const right = arr.slice(middle);
  
  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
  let result = [];
  let leftIndex = 0;
  let rightIndex = 0;
  
  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] < right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex++;  {
    if (left[leftIndex] < right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex++;
    } else {
      result.push(right[rightIndex]);
      rightIndex++;
    }
  }
  
  // We need to concatenate the remaining elements
  // This is where the bug is - we're not adding remaining elements
  return result;
}

Console

Run your code to see output here

Previous ChallengeNext Challenge

Exit