MergeSort linked list implementation
2
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 //<< "it"
<< "runtimet" << 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.
c++ performance complexity mergesort
edited 8 mins ago
Jamal♦
30.3k11116226
asked 9 hours ago
Rick
1114
New contributor
Rick is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
|
show 3 more comments
2
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 //<< "it"
<< "runtimet" << 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.
c++ performance complexity mergesort
edited 8 mins ago
Jamal♦
30.3k11116226
asked 9 hours ago
Rick
1114
New contributor
Rick is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
2
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?
– Quuxplusone
9 hours ago
2
To see why your algorithm isO(n^2), look at how eachmergecallsgetIndexPointer. How many times do you callmerge? How many times do you callgetIndexPointer? What is the big-O ofgetIndexPointer? (In particular, what is the difference in big-O between your version ofgetIndexPointerfor linked lists and the textbook's version ofgetIndexPointerfor arrays?)
– Quuxplusone
9 hours ago
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'tusing namespace std;" or "a global variable of typerandom_deviceis really strange" — indeed CodeReview is the place (but you can delete all the tables of timings).
– Quuxplusone
8 hours ago
2
@Quuxplusone Damn you are amazing and I am being so stupid. It's indeedO(n^2). I just ignore that factor 4 characteristic... 😭. Also I do a power function regression in Excel and R square = 99.43% 😭.
– Rick
8 hours ago
1
Yep, if you could avoid modifying the algorithm and keep that single loop, it'd beO(n lg n). But since you added a second, nested, loop, ingetIndexPointer(another factor ofO(n)), the result isO(n lg n) * O(n) = O(n^2 lg n). (Or thereabouts. I didn't even bother with the factor oflg nbecause, as a wise man once said,lg nis about 30.)
– Quuxplusone
8 hours ago
|
show 3 more comments
2
2
2
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 //<< "it"
<< "runtimet" << 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.
c++ performance complexity mergesort
edited 8 mins ago
Jamal♦
30.3k11116226
asked 9 hours ago
Rick
1114
New contributor
Rick is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
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 //<< "it"
<< "runtimet" << 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.
c++ performance complexity mergesort
c++ performance complexity mergesort
edited 8 mins ago
Jamal♦
30.3k11116226
asked 9 hours ago
Rick
1114
New contributor
Rick is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 8 mins ago
Jamal♦
30.3k11116226
asked 9 hours ago
Rick
1114
New contributor
Rick is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 8 mins ago
Jamal♦
30.3k11116226
edited 8 mins ago
Jamal♦
30.3k11116226
edited 8 mins ago
Jamal♦
30.3k11116226
30.3k11116226
asked 9 hours ago
Rick
1114
New contributor
Rick is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 9 hours ago
Rick
1114
asked 9 hours ago
Rick
1114
1114
New contributor
Rick is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Rick is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Rick is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
2
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?
– Quuxplusone
9 hours ago
2
To see why your algorithm isO(n^2), look at how eachmergecallsgetIndexPointer. How many times do you callmerge? How many times do you callgetIndexPointer? What is the big-O ofgetIndexPointer? (In particular, what is the difference in big-O between your version ofgetIndexPointerfor linked lists and the textbook's version ofgetIndexPointerfor arrays?)
– Quuxplusone
9 hours ago
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'tusing namespace std;" or "a global variable of typerandom_deviceis really strange" — indeed CodeReview is the place (but you can delete all the tables of timings).
– Quuxplusone
8 hours ago
2
@Quuxplusone Damn you are amazing and I am being so stupid. It's indeedO(n^2). I just ignore that factor 4 characteristic... 😭. Also I do a power function regression in Excel and R square = 99.43% 😭.
– Rick
8 hours ago
1
Yep, if you could avoid modifying the algorithm and keep that single loop, it'd beO(n lg n). But since you added a second, nested, loop, ingetIndexPointer(another factor ofO(n)), the result isO(n lg n) * O(n) = O(n^2 lg n). (Or thereabouts. I didn't even bother with the factor oflg nbecause, as a wise man once said,lg nis about 30.)
– Quuxplusone
8 hours ago
|
show 3 more comments
2
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?
– Quuxplusone
9 hours ago
2
To see why your algorithm isO(n^2), look at how eachmergecallsgetIndexPointer. How many times do you callmerge? How many times do you callgetIndexPointer? What is the big-O ofgetIndexPointer? (In particular, what is the difference in big-O between your version ofgetIndexPointerfor linked lists and the textbook's version ofgetIndexPointerfor arrays?)
– Quuxplusone
9 hours ago
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'tusing namespace std;" or "a global variable of typerandom_deviceis really strange" — indeed CodeReview is the place (but you can delete all the tables of timings).
– Quuxplusone
8 hours ago
2
@Quuxplusone Damn you are amazing and I am being so stupid. It's indeedO(n^2). I just ignore that factor 4 characteristic... 😭. Also I do a power function regression in Excel and R square = 99.43% 😭.
– Rick
8 hours ago
1
Yep, if you could avoid modifying the algorithm and keep that single loop, it'd beO(n lg n). But since you added a second, nested, loop, ingetIndexPointer(another factor ofO(n)), the result isO(n lg n) * O(n) = O(n^2 lg n). (Or thereabouts. I didn't even bother with the factor oflg nbecause, as a wise man once said,lg nis about 30.)
– Quuxplusone
8 hours ago
2
2
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?
– Quuxplusone
9 hours ago
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?
– Quuxplusone
9 hours ago
2
2
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?)– Quuxplusone
9 hours ago
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?)– Quuxplusone
9 hours ago
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).– Quuxplusone
8 hours ago
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).– Quuxplusone
8 hours ago
2
2
@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% 😭.– Rick
8 hours ago
@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% 😭.– Rick
8 hours ago
1
1
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.)– Quuxplusone
8 hours ago
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.)– Quuxplusone
8 hours ago
|
show 3 more comments
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
});
});
}, "mathjax-editing");
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "196"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Rick is a new contributor. Be nice, and check out our Code of Conduct.
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f210750%2fmergesort-linked-list-implementation%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
Rick is a new contributor. Be nice, and check out our Code of Conduct.
draft saved
draft discarded
Rick is a new contributor. Be nice, and check out our Code of Conduct.
Rick is a new contributor. Be nice, and check out our Code of Conduct.
Rick is a new contributor. Be nice, and check out our Code of Conduct.
Thanks for contributing an answer to Code Review Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f210750%2fmergesort-linked-list-implementation%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
2
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?
– Quuxplusone
9 hours ago
2
To see why your algorithm is
O(n^2), look at how eachmergecallsgetIndexPointer. How many times do you callmerge? How many times do you callgetIndexPointer? What is the big-O ofgetIndexPointer? (In particular, what is the difference in big-O between your version ofgetIndexPointerfor linked lists and the textbook's version ofgetIndexPointerfor arrays?)– Quuxplusone
9 hours ago
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 typerandom_deviceis really strange" — indeed CodeReview is the place (but you can delete all the tables of timings).– Quuxplusone
8 hours ago
2
@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% 😭.– Rick
8 hours ago
1
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, ingetIndexPointer(another factor ofO(n)), the result isO(n lg n) * O(n) = O(n^2 lg n). (Or thereabouts. I didn't even bother with the factor oflg nbecause, as a wise man once said,lg nis about 30.)– Quuxplusone
8 hours ago