performance - 两个未排序的单链表到一个排序的单链表

Question

M给定两个大小为和的未排序单链表N。任务是创建一个单一的排序链表。不应创建新节点。我想到了两种方法。

方法一：

在 MlogM 和 NlogN 中分别对每个列表进行排序。然后合并两个排序列表。
时间复杂度：O( MlogM + NlogN )

方法二：

将第二个列表附加到第一个列表的末尾。然后对列表进行排序。
时间复杂度： O( (M + N) log(M + N) )

哪种方法更好？
还有更好的方法吗？

Answer 1

渐近地说 - 它是一样的。

如果n<m那时：

O(nlogn+ mlogm) = O(mlogm)
and 
O(n+m)log(n+m)) = O(nlog(n+m) + mlog(n+m)) = O(nlog(m) + mlog(m)) = O(mlogm)

对称地，如果m<n两者都是O(nlogn)

实际上，对于，方法一是归并排序n=m的第一步

Answer 2

无论如何，方法 1 是好的。请参阅此计算，如果

• n=2 和 m=3 nlogn = 0.60，mlogm = 1.43，nlogn + mlogm = 2.03 而 (n+m)log(n+m) = 3.49

• n=2 和 m=30 nlogn = 0.60，mlogm = 44.31，nlogn + mlogm = 44.91 而 (n+m)log(n+m) = 48.16

• n=2 和 m=300 nlogn = 0.60, mlogm = 743.14, nlogn + mlogm = 743.74
  而 (n+m)log(n+m) = 748.96

• n=2 和 m=3000 nlogn = 0.60, mlogm = 10,431.36, nlogn + mlogm =
  10,431.96 而 (n+m)log(n+m) = 10,439.18

• n=2 和 m=30000 nlogn = 0.60, mlogm = 134,313.64, nlogn + mlogm =
  134,314.24 而 (n+m)log(n+m) = 134,323.46

• n=2 和 m=300000 nlogn = 0.60 ,mlogm = 1,643,136.38, nlogn + mlogm = 1,643,136.98 而 (n+m)log(n+m) = 1,643,148.19

因为，这背后的明确原因是：无论如何，

(n+m) > n & (n+m) > m
log (n+m) >= log n
log (n+m) >= log m

而在 n=m 的情况下，

nlogn + mlogm = 2m logm
              = log m (power of 2m)
(n+m) log(n+m) = 2m log (2m)
               = log 2m (power of 2m)
and m(power of 2m) < 2m(power of 2m)

选择第一种方法的唯一简单原因是，与大数组相比，对小数组进行排序花费更少的时间。