calculating time complexity of merging presorted lists without using extra memory

Vote count: 0

Given a list of presorted arrays, i.e. List<List<Integer>>, I am using the following technique to sort them. Will someone please explain to me the time complexity? Here is the algorithm

List<Integer> merge(List<List<Integer>> lists){
    Queue<MyPriorityQueue> pqs = new LinkedList<>();
    for(int i=1; i<lists.size();i+=2){
        pqs.add(merge(lists.get(i-1),lists.get(i)));
    }
    if(lists.size()%2==1)pqs.add(merge(lists.get(lists.size()-1),null));

    while(pqs.size()>1) pqs.add( merge(pqs.poll(),pqs.poll()));

    MyPriorityQueue myPq = pqs.poll();
    List<Integer> results = new ArrayList<>();

    while(!myPq.isEmpty()){
        result.add(myPq.poll());
    }
    return result;
}

There are two merge methods.

MyPriorityQueue merge(List<Integer> a, List<Integer> b){ return new MyPriorityQueue(a,b);}

MyPriorityQueue merge(MyPriorityQueue a, MyPriorityQueue  b){ return new MyPriorityQueue(a,b);}

Notice that the merge function essentially passes two iterators to the MyPriorityQueue constructor. So that when a call is made to MyPriorityQueue#poll(), the two iterators are compared and the greater value is returned. Hence, we are not using extra memory.

Now let’s compare to normal mergeSort. Normally mergeSort uses extra memory: each call to merge(x, y) would simply create a third list z and put all the elements in x and y into z. That approach would result in time O(n lg n). But in my present approach, we are not using the extra memory. So that each time I call #poll(), I have to walk the tree to find the smallest element. This to me means O(n^2) for the line while(!myPq.isEmpty()){result.add(myPq.poll());}. But someone had told me that the time complexity is actually still O(n lg n). I can’t see how. Will someone please explain the time complexity to me?

We are not doing log n comparisons a number of n times, are we? Per my visualization, if there are n lists on the tree and I call myPq.poll()), then we are doing n comparisons.

So basically let's say there are n lists and each list has an average of k elements in them. The time complexity of the algorithm seems to me

log n + (n+k)*n. It takes log n to create the pqs tree and get the root; then it takes (n+k)*n to add all the elements to result as while(!myPq.isEmpty()){result.add(myPq.poll());}

asked 32 secs ago

Nouvel Travay

Let's block ads! (Why?)

calculating time complexity of merging presorted lists without using extra memory