[a, b, c] и [d, e, f]
«a» необходимо сравнить с «d» и «e» и «f» наихудшим сценарием.
l oop
while (not at end of A && not at end of B)
всегда имеет O (| A | + | B |) шагов, независимо от результатов сравнения. Для слияния и подсчета не существует ни лучшего, ни худшего случая.
Сортировка и подсчет (L)
if list L has one element
return (0, L)
Divide the list into two halves A and B
(rA, A) ← Sort-and-Count(A)
(rB, B) ← Sort-and-Count(B)
(rC, L) ← Merge-and-Count(A, B)
r = rA + rB + rC
return (r, L)
Слияние -и-Счетчик (A, B)
curA = 0; curB = 0;
count = 0;
mergedList = empty list
while (not at end of A && not at end of B)
a = A[curA]; b = B[curB];
if (a < b) // only one comparison
append a to mergedList;
curA++;
else
append b to mergedList;
curB++;
count = count + num elements left in A
if (at end of A)
append rest of B to mergedList;
else
append rest of A to mergedList;
return (count, mergedList);