Question 185748 in Javascript Question posted in
A very good W3school tutorial can be found here.

Javascript – What is the difference between both the sample?

Sample 1:

function mergesort(arr){
    if (arr.length > 1){
        let mid = parseInt(arr.length/2);
        let left = arr.slice(0,mid);
        let right = arr.slice(mid);
        mergesort(left);
        mergesort(right);  
        return merge(left,right);
    }
    else return arr;
}

Sample 2:

function mergesort(arr){
    if (arr.length > 1){
        let mid = parseInt(arr.length/2);
        let left = mergesort(arr.slice(0,mid));
        let right = mergesort(arr.slice(mid));   
        return merge(left,right);
    }
    else return arr;
}

Merge function:

function merge(left, right){
    let leftIdx = 0, rightIdx = 0; 
    const result = [];
    while (leftIdx < left.length && rightIdx < right.length){
        if (left[leftIdx] < right[rightIdx]){
            result.push(left[leftIdx++])
        }
        else{
            result.push(right[rightIdx++])
        }
    }
    let res = [...result, ...left.slice(leftIdx), ...right.slice(rightIdx)];
    return res;

Sample 2 is giving the correct output but sample 1 is not. Can you explain the difference between both samples?

let arr = [5, 3, 7, 2, 9, 12, 4];

Applying sample 1 on arr gives [2, 5, 3, 7, 9, 12, 4] as output that is obviously incorrect.

Tags:

3

Answers


  1. 0

    You have to change these two lines

    mergesort(left);
mergesort(right);

    to

    left = mergesort(left);
right = mergesort(right);

    Otherwise you are continuing to work with the unsorted arrays.

    Login or Signup to reply.
  2. 0

    Your first code sample does not work because you did not assign the output of mergesort to a new variable.

    Try it like this instead:

    function mergesort(arr){
    if (arr.length > 1){
        let mid = parseInt(arr.length/2);
        let left = arr.slice(0,mid);
        let right = arr.slice(mid);
        left = mergesort(left);
        right = mergesort(right);  
        return merge(left,right);
    }
    else return arr;
}
    Login or Signup to reply.
  3. 0

    The difference between the two samples lies in how the left and right arrays are created and passed recursively in the mergesort function.

    In sample 1, the left and right arrays are created using the arr.slice() method after finding the midpoint. Then, mergesort is called recursively on left and right. However, the resulting sorted arrays from these recursive calls are not assigned to any variables. Therefore, when merge(left, right) is called, it operates on the original left and right arrays, which are still unsorted. This leads to an incorrect result.

    In sample 2, the left and right arrays are created using the mergesort(arr.slice()) calls directly when assigning them to variables. This means that the recursive calls return the sorted arrays, which are then properly assigned to left and right. Consequently, when merge(left, right) is called, it operates on the correctly sorted arrays, resulting in the correct output.

    To fix sample 1, you would need to assign the returned values of the recursive mergesort calls to left and right before calling merge(left, right).

    Here’s an updated version of sample 1:

    function mergesort(arr){
    if (arr.length > 1){
        let mid = parseInt(arr.length/2);
        let left = arr.slice(0,mid);
        let right = arr.slice(mid);
        left = mergesort(left); // assign the returned value to left
        right = mergesort(right); // assign the returned value to right
        return merge(left,right);
    }
    else return arr;
}

    With this modification, both sample 1 and sample 2 should produce the correct output. MADE WITH THE HELP OF CHAT GPT.

    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search