2
\$\begingroup\$

I wrote a MergeSort implementation of doubly linked list, based on the MergeSort implementation of array on the textbook Algorithms 4th, which is definitely \$O(n \log n)\$.

I think my linked list implementation is \$O(n \log n)\$, but it runs so much slower than the array version so I am getting very confused and doubting!

Is my linked list implementation \$O(n \log n)\$ time complexity? If it is, then is it normal that it's so much slower than the array version? If it's not, where did I make mistakes?

Besides, anything that natively, hugely improve the linked list version's performance is appreciated. (For simplicity, I do not use template every where, this can be put aside first.)

Linked list version:

doublelinkedlist.h

#pragma once
#include <stdexcept>
#include <iostream>
#include <initializer_list>
namespace ythlearn{
    template<typename T>
    class DLinkList{
    public:
        class Node{
        public:
            Node* next;
            Node* prev;
            T elem;
        };
        Node head;
        Node tail;
        int _size;
        bool linked;
    public:
        DLinkList(){
            head.next = head.prev = tail.next = tail.prev = nullptr;
            _size = 0;
            linked = false;
        }

        DLinkList(std::initializer_list<T> init_list){
            head.next = head.prev = tail.next = tail.prev = nullptr;
            _size = 0;
            linked = false;
            for(auto s = init_list.begin(); s!=init_list.end(); s++){
                push_right(*s);
            }
        }

        int size(){
            return _size;
        }

        bool isEmpty(){
            return size() == 0;
        }

        Node* getIndexPointer(int index){
            if(index >= size()){
                throw std::runtime_error("getIndexPointer index overflow");
            }else{
                int i = 0;
                Node* n_ptr = head.next;
                while(i != index){
                    n_ptr = n_ptr->next;
                    i++;
                }
                return n_ptr;
            }
        }

        Node* getIndexPointer(Node* start_position_ptr, int distance){
            if(distance >= size()){
                throw std::runtime_error("getIndexPointer(with start_position) index overflow");
            }else{
                int i = 0;
                Node* n_ptr = start_position_ptr;
                while(i != distance){
                    n_ptr = n_ptr->next;
                    i++;
                }
                return n_ptr;
            }
        }

        bool isSorted(){
            Node* n_ptr = head.next;
            while(n_ptr != tail.next->prev){
                if(n_ptr->elem > n_ptr->next->elem)
                    return false;
                n_ptr = n_ptr->next;
            }
            return true;
        }

        DLinkList& push_right(T elem){
            Node* n = new Node;
            n->elem = elem;
            if(isEmpty()){
                head.next = tail.next = n;
                n->next = n->prev = n;
            }else{
                n->next = head.next;
                n->prev = tail.next;
                tail.next->next = n;
                tail.next = n;
                head.next->prev = tail.next;
            }
            ++_size;
            return *this;
        }

        DLinkList& push_left(T elem){
            //deleted for simplicity
        }


        T pop_left(){
            //deleted for simplicity
        }

        T pop_right(){
            //deleted for simplicity
        }

        void print(){
            //deleted for simplicity
        }

        DLinkList(const DLinkList&) = delete;
        DLinkList& operator=(const DLinkList&) const = delete;
        ~DLinkList(){
            if(!linked){
                Node* node_to_delete;
                while(head.next != tail.next){
                    node_to_delete = head.next;
                    head.next = head.next->next;
                    delete node_to_delete;
                }
                delete tail.next;
            }
        }

    };
}

mergeSortTopDownLinkedList.h:

#pragma once
#include "doublelinkedlist.h"

class MergeTopDown{
public:
    static void sort(ythlearn::DLinkList<int> &a){
        sort(a, 0, a.size() - 1);
    }
private:
    static void sort(ythlearn::DLinkList<int> &a, int lo, int hi){
        int mid = lo + (hi - lo) / 2;
        if(hi <= lo) return;
        sort(a, lo, mid);
        sort(a, mid+1, hi);
        merge(a, lo, mid, hi);
    }
public:
    static void merge(ythlearn::DLinkList<int> &a, int lo, int mid, int hi){

        auto loPtr = a.getIndexPointer(lo);
        auto midPtr = a.getIndexPointer(loPtr, mid - lo);
        auto midPlus1 = midPtr->next;
        auto hiPtr = a.getIndexPointer(midPtr, hi - mid);

        //if it's not sorted from head to tail, then need these two helper Node
        auto NodePtrBeforeLo = loPtr->prev;
        auto NodePtrAfterHi = hiPtr->next;

        //split them into 2 isolated chains
        midPtr->next = nullptr;
        hiPtr->next = nullptr;

        ythlearn::DLinkList<int>::Node newList;
        decltype(loPtr) newListPtr = &newList;

        while(loPtr != nullptr && midPlus1 != nullptr){
            if(loPtr->elem < midPlus1->elem){
                newListPtr->next = loPtr;
                loPtr->prev = newListPtr;
                loPtr = loPtr->next;
                newListPtr = newListPtr->next;
            }else{
                newListPtr->next = midPlus1;
                midPlus1->prev = newListPtr;
                midPlus1 = midPlus1->next;
                newListPtr = newListPtr->next;
            }
        }

        if(loPtr == nullptr){
            newListPtr->next = midPlus1;
            midPlus1->prev = newListPtr;
            if(hi-lo != a.size() - 1){
                NodePtrAfterHi->prev = hiPtr;
                hiPtr->next = NodePtrAfterHi;
            }
            if(hi == a.size() - 1){
                a.tail.next = hiPtr;
            }
        }else{
            newListPtr->next = loPtr;
            loPtr->prev = newListPtr;
            if(hi-lo != a.size() - 1){
                NodePtrAfterHi->prev = midPtr;
                midPtr->next = NodePtrAfterHi;
            }
            if(hi == a.size() - 1){
                a.tail.next = midPtr;
            }
        }

        //Insert it back
        if(hi - lo != a.size() - 1){
            NodePtrBeforeLo->next = newList.next;
            newList.next->prev = NodePtrBeforeLo;
        }

        if(lo == 0){
            a.head.next = newList.next;
        }

    }
};

main.cpp:

#include <iostream>
#include <random>
#include "doublelinkedlist.h"
#include "mergeSortTopDownLinkedList.h"
#include <chrono>
using namespace std;
using namespace ythlearn;
using namespace std::chrono;

random_device rd;
mt19937 e(rd());
uniform_int_distribution<int> dist(INT16_MIN, INT16_MAX);

int main(){
    cout //<< "i\t"
            << "runtime\t" << endl;

    for(int i = 32; true; i = i * 2){
        DLinkList<int> dl;
        for(int j = 0; j < i; j++){
            dl.push_right(dist(e));
        }
        auto start = high_resolution_clock::now();
        MergeTopDown::sort(dl);
        auto stop = high_resolution_clock::now();
        auto duration = duration_cast<microseconds>(stop - start);
        cout <<  duration.count() << endl;
    }
    return 0;
}

Array (std::vector) version:

mergeSortTopDown.h:

#pragma once
#include <vector>
#include <iostream>

class MergeTopDown{
public:
    static void sort(std::vector<int> &a, std::vector<int> &aux){
        sort(a, aux, 0, a.size() - 1);
    }
private:
    static void sort(std::vector<int> &a, std::vector<int> &aux, int lo, int hi){
        int mid = lo + (hi - lo) / 2;
        if(hi <= lo) return;
        sort(a, aux, lo, mid);
        sort(a, aux, mid+1, hi);
        merge(a, aux, lo, mid, hi);
    }
    static void merge(std::vector<int> &a, std::vector<int> &aux, int lo, int mid, int hi){
        for(int k = lo; k <= hi; k++){
            aux[k] = a[k];
        }

        int i = lo, j = mid+1;

        for(int k = lo; k <= hi; k++){
            if(i > mid){
                a[k] = aux[j++];
            }else if (j > hi){
                a[k] = aux[i++];
            }else if(aux[i] < aux[j]){
                a[k] = aux[i++];
            }else{
                a[k] = aux[j++];
            }
        }
    }
};

main.cpp:

#include <iostream>
#include <vector>
#include <random>
#include <chrono>
#include "mergeSortTopDown.h"
using namespace std::chrono;
using namespace std;

random_device rd;
mt19937 e(rd());
uniform_int_distribution<int> dist(INT16_MIN, INT16_MAX);

int main(){
    for(int i = 32; true ; i = i * 2){
        vector<int> a(i);
        vector<int> aux(i);


        for(int j = 0; j < i ; j++){
            a[j] = dist(e);
        }

        auto start = high_resolution_clock::now();
        MergeTopDown::sort(a, aux);
        auto stop = high_resolution_clock::now();
        auto duration = duration_cast<microseconds>(stop - start);
        cout <<  duration.count() << endl;

    }
    return 0;
}

Runtime test

Array (vector):

                MergeSort Array 
input   output(runtime, milliseconds)   seconds
32          0                               0
64          0                               0
128         0                               0
256         0                               0
512         0                               0
1024        0                               0
2048        0                               0
4096        1                               0.001
8192        2                               0.002
16384       6                               0.006
32768       14                              0.014
65536       28                              0.028
131072      60                              0.06
262144      126                             0.126
524288      262                             0.262
1048576     548                             0.548
2097152     1206                            1.206
4194304     2347                            2.347
8388608     4847                            4.847
16777216    10353                           10.353
33554432    21698                           21.698

Linked list:

        MergeSort Doubly Linked List    
input   output(runtime, milliseconds)   seconds
32              0                           0
64              0                           0
128             0                           0
256             0                           0
512             0                           0
1024            2                           0.002
2048            11                          0.011
4096            47                          0.047
8192            237                         0.237
16384           1310                        1.31
32768           6440                        6.44
65536           29737                       29.737
131072          209752                      209.752

262144          Too long to wait    
524288      
1048576     
2097152     
4194304     
8388608     
16777216        
33554432        

As you can see the linked list version is sooo much slower than the array one. Take input size of 65536 as example, 0.028s vs 29.737s.

\$\endgroup\$
  • 2
    \$\begingroup\$ The big-O question isn't really on-topic for CodeReview. But you can figure out the answer yourself! When you double N (say, from 8194 to 16384, or from 16384 to 32768, or from 32768 to 65536), what happens to the running time of your code? It goes up by a factor of 4, right? So what is the big-O here? \$\endgroup\$ – Quuxplusone Jan 2 at 16:47
  • 2
    \$\begingroup\$ To see why your algorithm is O(n^2), look at how each merge calls getIndexPointer. How many times do you call merge? How many times do you call getIndexPointer? What is the big-O of getIndexPointer? (In particular, what is the difference in big-O between your version of getIndexPointer for linked lists and the textbook's version of getIndexPointer for arrays?) \$\endgroup\$ – Quuxplusone Jan 2 at 16:50
  • \$\begingroup\$ Really, I don't think you should post the big-O question anywhere. You're just posting O(n^2) code disguised in a bunch of nested function calls and asking "why is this O(n^2)?" The answer is "because it does O(n^2) work." There's no answer there that would be of general interest to the StackExchange community. If you want a review on the code — things like "don't using namespace std;" or "a global variable of type random_device is really strange" — indeed CodeReview is the place (but you can delete all the tables of timings). \$\endgroup\$ – Quuxplusone Jan 2 at 17:00
  • 2
    \$\begingroup\$ @Quuxplusone Damn you are amazing and I am being so stupid. It's indeed O(n^2). I just ignore that factor 4 characteristic... 😭. Also I do a power function regression in Excel and R square = 99.43% 😭. \$\endgroup\$ – Rick Jan 2 at 17:12
  • 1
    \$\begingroup\$ Yep, if you could avoid modifying the algorithm and keep that single loop, it'd be O(n lg n). But since you added a second, nested, loop, in getIndexPointer (another factor of O(n)), the result is O(n lg n) * O(n) = O(n^2 lg n). (Or thereabouts. I didn't even bother with the factor of lg n because, as a wise man once said, lg n is about 30.) \$\endgroup\$ – Quuxplusone Jan 2 at 17:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.