Javascript calling function from within function

Question

function newsort(array) {
    if (array.length <= 1) {
        alert(array);
    } else {
        mid = array.length / 2;
        left = [];
        right = [];
        for (i = 0; i < mid; i++) {
            left.push(array[i]);
        }
        for (i = mid; i <= array.length; i++) {
            right.push(array[i]);
        }
    }
    result = merge(left, right);
    alert(result);
};

function merge(left, right) {
    alert(left);
}

function merge(arr1, arr2) {
    var arr3 = [];
    while (arr1.length > 0 && arr2.length > 0) {
        if (arr1[0] <= arr2[0]) {
            arr3.push(arr1.shift());
        } else {
            arr3.push(arr2.shift());
        }
    }

    while (arr1.length > 0) {
        arr3.push(arr1.shift());
    }

    while (arr2.length > 0) {
        arr3.push(arr2.shift());
    }
    //  time = timeSortingAlgorithm(arr3, newsort(array));
    //  return time;
    return arr3;
};

function makeRandomArray(size) {
    var result = Array();
    while (size > 0) {
        result.push(Math.floor(Math.random() * 100000));
        --size;
    }
    return result;
}

function timeSortingAlgorithm(array, sortingAlgorithm) {
    var startTime = new Date();
    newsort(array);
    var endTime = new Date();
    return endTime.getTime() - startTime.getTime();
}

var array = makeRandomArray(6);
newsort(array);
//timeSortingAlgorithm(array,newsort);

When I run this code, the idea is that it will take the function merge and send the two halves of the array to newsort - which then merges them together, sorted. The array is created by the makeRandomArray function. However, I cannot figure out how to incorporate the timeSortingAlgorithm(array, sortingAlgorithm) function, as when I call it - nothing happens. I have the calls commented out at the moment, but when I take those out - no output at all. If I leave that function out of the process altogether - everything works fine.

Anyone able to point me in the right direction?

Answer 1

Three is a major problem with your implementation.

1. If you are trying to implement Merge Sort, the array has to be split and the split parts have to be sorted before merging.

Apart from that, the problems which I could find are

1. You are using global variables, mid, left and right are global variables.

2. You don't return the sorted arrays back from newsort function.

3. You have two merge functions defined.

4. Your mid should be an integer, as you are using that for indexing an array and that will return undefined for floating point numbers.

So, the fixed implementation looks like this

function newsort(array) {
    if (array.length <= 1) {
        return array;
    } else {
        var mid   = parseInt(array.length / 2), left  = [], right = [];
        for (var i = 0; i < mid; i++) {
            left.push(array[i]);
        }
        for (i = mid; i < array.length; i++) {
            right.push(array[i]);
        }
    }
    return merge(newsort(left), newsort(right));
};

function merge(arr1, arr2) {
    var arr3 = [];
    while (arr1.length > 0 && arr2.length > 0) {
        if (arr1[0] <= arr2[0]) {
            arr3.push(arr1.shift());
        } else {
            arr3.push(arr2.shift());
        }
    }

    while (arr1.length > 0) {
        arr3.push(arr1.shift());
    }

    while (arr2.length > 0) {
        arr3.push(arr2.shift());
    }
    return arr3;
};

function timeSortingAlgorithm(array, sortingAlgorithm) {
    var startTime = new Date(), result = sortingAlgorithm(array);
    console.log(new Date().getMilliseconds() - startTime.getMilliseconds());
    return result;
}

var array = makeRandomArray(6);
console.log(array);
console.log(timeSortingAlgorithm(array, newsort));

Answer 2

You are having an infinite loop.

when you run this line :

time = timeSortingAlgorithm(arr3, newsort(array));

You call newsort.

newsort call the function merge which then run over, guess what, this line :

time = timeSortingAlgorithm(arr3, newsort(array));