Сортировка слиянием Время и пространственная сложность

Давайте возьмем эту реализацию сортировки слиянием в качестве примера

void mergesort(Item a[], int l, int r) {
if (r <= l) return;
int m = (r+l)/2;
mergesort(a, l, m);  ------------ (1)
mergesort(a, m+1, r); ------------(2)
merge(a, l, m, r);

a )Временная сложность этой сортировки слиянием составляет O (nlg (n )). Даст ли распараллеливание (1 )и (2 )какой-либо практический выигрыш? Теоретически получается, что после их распараллеливания вы также получите O (nlg (n ). Но практически можем ли мы получить какие-либо выгоды?

b )Пространственная сложность этой сортировки слиянием здесь O (n ). Однако, если я решу выполнить в -сортировку слиянием места с использованием связанных списков (не уверен, что это можно сделать с массивами разумно )станет ли пространственная сложность O (lg (n )), так как вы должны учитывать размер кадра стека рекурсии? Можем ли мы рассматривать O (lg (n ))как константу, поскольку она не может быть больше 64? Возможно, я неправильно понял это в нескольких местах. Каково именно значение 64 ?

c)http://www.cprogramming.com/tutorial/computersciencetheory/sortcomp.htmlговорит, что сортировка слиянием требует постоянного пространства при использовании связанных списков. Как ? Считали ли они O (lg (n )постоянным?

d )[Добавлено для большей ясности] Справедливо ли для расчета пространственной сложности предположить, что входной массив или список уже находятся в памяти? Когда я выполняю расчеты сложности, я всегда вычисляю «дополнительное» пространство, которое мне понадобится, помимо пространства, уже занятого вводом. В противном случае пространственная сложность всегда будет O (n )или хуже.