Merge sort is giving "time limit exceeded" error (TSORT)

,
1 
var arr = '',a = [];
process.stdin.on('data',function(chunk){
   arr += chunk; 
});

process.stdin.on('end',function(){
    arr = arr.split('\n');
    let t = parseInt(arr[0]);
    for(var i =1;i<=t;i++){
       a[i-1]=parseInt(arr[i]);
    }
    let final_array = mergeSort(a);
    for(var k=0;k<final_array.length;k++){
        console.log(final_array[k]);
    }
});

function mergeSort(a){
    if(a.length === 1){
        return a;
    }else{
        let midpoint = parseInt(a.length/2);
        let left_arrr = a.slice(0,midpoint);
        let right_arrr = a.slice(midpoint,a.length);
        return merge(mergeSort(left_arrr),mergeSort(right_arrr));
    }
}

function merge(leftArr,rightArr){
    let sortedArr = [],i=0,j=0;
    if((left_arr.length === 1) && (right_arr.length === 1)){
        (left_arr[0] < right_arr[0])?sortedArr.push(left_arr[0],right_arr[0]):sortedArr.push(right_arr[0],left_arr[0]);
    }else{
        while((i<left_arr.length) && (j<right_arr.length)){
            (left_arr[i] < right_arr[j])?(sortedArr.push(left_arr[i]),i++):(sortedArr.push(right_arr[j]),j++);
        }
        while(i<left_arr.length){
            sortedArr.push(left_arr[i]);
            i++;
        }
       while(j<right_arr.length){
            sortedArr.push(right_arr[j]);
            j++;
       }
   }
   return sortedArr;
}

What is wrong in my code?Atleast an hint where i am wrong so that i can debug and try myself.

2

I’m not a nodejs guy, but I just tried your code (after fixing the errors - left_arr and right_arr should be leftArr and rightArr respectively), and it looks like outputting the results one by one with console.log takes up the bulk of the time.

Other solutions seem to be combining all output into one string and dumping that out i.e.

console.log(final_array.join('\n'));

This is much faster in my tests, though I don’t know whether it’s fast enough. Frankly, I’d just use the built-in sort method, personally :slight_smile:

4 Likes
3

@ssjgz thanks for helping, that was the only issue that you pointed out. But I wanted to know that loop was giving the time complexity O(n) and same “join” will be giving then why my solution was not working?

1 Like
4

The two methods of output have (I presume) the same asymptotic performance (O(N)), but printing line-by-line is slower by a constant factor.

4 Likes
5

@ssjgz ok thank you

1 Like
6

@sweta787 I suppose the problem link is Turbo Sort.
If you look at the constraints in the problem: the value of 0 \leq a[i] \leq 10^6 where a[i] is element at the i^{th} location, so instead of using traditional comparison-based sorting algorithm like Merge Sort and Quick-Sort, you can use Linear Bound Sorting Algorithm as all the data in the array are integers. For example, you can use Counting Sort to solve the problem which will solve the problem in O(max(a[i])) which in this problem statement is O(10^6) in worst-case scenario.
For understanding Counting Sort you can refer to the following link: Counting Sort Algorithm Tutorial.

If you still want to see the different implementation for solving the problem i.e using mergesort, quicksort, counting sort then you can refer to my solution Competitive-Programming/Code-Chef/Turbo-Sort at master · strikersps/Competitive-Programming · GitHub written in C and Python.

1 Like