0

I have tried the entire day, and can't seem to be able to find out why it is not working. I think that the problem is my skills with JavaScript language. I might be missing some concept on parameter passing. Can you please show me where is the error?

Here is my implementation, based on another implementation I wrote a year ago in C#, which can be found here.

So here is the code (you can try direct on Chromes console, just copy/paste and it will "work"):

function merge(A, p, q, r){
    var n1 = q - p + 1;
    var n2 = r - q;

    var i = 0;
    var j = 0;

    var L = [];
    while (i < n1){
        L.push(A[p + i++]);
    }

    var R = [];
    while(j < n2){
        R.push(A[q + j++ + 1]);
    }

    L.push(Number.MAX_VALUE);
    R.push(Number.MAX_VALUE);

    i = 0; 
    j = 0; 

    var k = p;
    while(k <= r){
        if(L[i] <= R[i]){
            A[k] = L[i];
            i = i + 1;
        }else{
            A[k] = R[j];
            j = j + 1;
        }

        k = k + 1;
    }
}

function mergeSort(A, p, r){
    console.log(A);

    if(p < r){
        var q = Math.floor((p + r) / 2);

        mergeSort(A, p, q); 
        mergeSort(A, q + 1, r);
        merge(A, p, q, r);
    }
}

function testMergeSort(array){
    var p = 0;
    var r = array.length - 1;

    console.log("BEFORE: " + array);

    mergeSort(array, p, r);

    console.log("AFTER: " + array);
    console.log("---------------------------------");
}

testMergeSort([5, 2, 4, 7, 1, 3, 2, 6]);
Community
  • 1
  • 1
Renato Gama
  • 16,431
  • 12
  • 58
  • 92
  • I did not checked your code properly, but I can tell you that it's much too long. A mergesort should be implementable in much less lines. – Kijewski Jul 24 '12 at 00:23
  • @Kay; Merge Sort algorithm = 5 lines, the rest, as you didn't notice is testing code. Merge algorithm is the same as described in Introduction to Algorithms (http://www.amazon.com/Introduction-Algorithms-Second-Edition-Thomas/dp/0262032937). You can see the code here too: http://renatogama.com/blog/imagens/algoritmo-de-merge.png – Renato Gama Jul 24 '12 at 00:27
  • Your variable names are poorly chosen. They may save a few keystrokes for you, but make your code well-nigh unintelligible to the rest of us... – Elliot Bonneville Jul 24 '12 at 00:29
  • I agree with you @ElliotBonneville I've just chosen this variable names to match the book example, after several attempts. – Renato Gama Jul 24 '12 at 00:31
  • 2
    Ah, okay, understood. I'm sorry that I can't be of any help other than criticizing your code... but I get a headache every time I look at it, to be honest. :-) – Elliot Bonneville Jul 24 '12 at 00:34
  • 1
    @RenatoGama I don't know if it's the resolution of my monitor, but I count some more than 5 lines in `merge(...)`. ;-) – Kijewski Jul 24 '12 at 00:37
  • @ElliotBonneville thanx, I understand you clearly. – Renato Gama Jul 24 '12 at 00:42
  • @Kay thats because youre counting the wrong function, take a look at mergeSort and discard the blank lines/logging line. – Renato Gama Jul 24 '12 at 00:42
  • @Kay, yes. Pointless discussion. – Renato Gama Jul 24 '12 at 00:46

1 Answers1

8

A simple typo:

if(L[i] <= R[i]){

should be

if(L[i] <= R[j]){
Daniel Fischer
  • 181,706
  • 17
  • 308
  • 431