在Internet上的搜索引擎经常需要对信息进行比较。例如，可以通过某个人对一些事物的排名来估计他

(或她)对各种不同信息的兴趣，从而实现个性化的服务。对于不同的排名结果可以用逆序来评价它们之间的差异。考虑1，2，…，n的排列i₁，i₂，...，i_n，如果其中存在i_j，i_k，使得j＜k但是i_j＞i_k，那么就称(i_j，i_k)是这个排列的一个逆序。一个排列含有逆序的个数称为这个排列的逆序数。例如，排列263451含有8个逆序(2，1)，(6，3)，(6，4)，(6，5)，(6，1)，(3，1)，(4，1)，(5，1)，它的逆序数就是8。显然，由1，2，…，n构成的所有n!个排列中，最小的逆序数是0，对应的排列就是12…n;最大的逆序数是n(n-1)/2，对应的排列就是n(n-1)…21。逆序数越大的排列与原始排列的差异度就越大。不难看到，如果使用顺序枚举逆序的蛮力算法来计算排列的逆序数，最坏情况下需要O(n²)的时间。利用二分归并排序算法Mergesort可以设计一个计数逆序的更好的算法，它仅使用O(nlog n)的时间。它的主要思想是：在递归调用算法分别对子数组L₁与L₂排序时，计数每个子数组内部的逆序;在归并排好序的子数组L₁与L₂的过程中，计数L₁的元素与L₂的元素之间产生的逆序。在算法运行中每次得到的逆序数都加到逆序总数上。下面是一个归并过程的例子。

假如两个排好序的子数组是1，4，5和2，3，6，在归并时，先比较1和2，1＜2，没有逆序，移走1，第一个数组剩下2个数;接着比较4和2，4＞2，第一个数组的4，5都与2构成逆序，即(4，2)，(5，2)，产生的逆序数恰好等于第一个数组剩下的元素个数。移走2，逆序总数加2。接着比较4和3，移走3，再增加2个逆序;接着比较4和6，移走4，不增加逆序;比较5和6，移走5，不增加逆序。在这个过程中逆序数共增加了4，恰好等于1，4，5与序列2，3，6的数之间构成的逆序总数。

(1)根据上面的描述写出算法的伪码。

(2)如果n是2的幂，计算算法使用的比较次数。