# C++ QuickSort 43ms beats 99.82%

• Considering recursive calls, the space complexity is actually O(logn), not O(1).

``````    // Quick Sort

}

ListNode* l;    // left half
ListNode* r;    // right half
ListNode* m;    // pivot
ListNode* lt;
ListNode* rt;
ListNode* mt;
ListNode d1(0); // dummy
ListNode d2(0);

// choose pivot and divide
l = &d1;
r = &d2;

// skip pivot
lt = l;
rt = r;
mt = m;

// divide
lt = lt->next;
} else if (head->val > m->val){
rt = rt->next;
} else {
mt = mt->next;
}
}

// handle tail
lt->next = nullptr;
rt->next = nullptr;
mt->next = nullptr;

// remove dummy
l = l->next;
r = r->next;

// recursive step
l = sortList(l);
r = sortList(r);

// merge
if (!l) {
mt->next = r;
} else {
lt = l;
while (lt->next) lt = lt->next; // find the tail of left half
lt->next = m;
mt->next = r;
}
}
``````

• Merge sort 59 ms:

``````    // Merge Sort

while (fast && fast->next) {
fast = fast->next->next;
tail = slow;
slow = slow->next;
}

tail->next = nullptr;
ListNode* h2 = sortList(slow);

ListNode dummy(0);
while (h1 && h2) {
if (h1->val < h2->val) {
h1 = h1->next;
} else {