Hi, On 2022/6/26 03:30, Thomas Schmitt wrote:
Complexity-wise this replaces a slow O(n) algorithm by a faster O(n) and an additional O(n * log(n)) run. At some size of Debian the slow speed of the linear loop will be compensated by the sorting complexity. But there is still room: A sort of 11,000 lines lasts about 0.03 seconds.
Theoretically if both file is already sorted, we can use the `-m' option (e.g. `sort -m -k 2 A.txt B.txt') to merge them in O(n) like mergesort. However I don't think O(n * log(n)) is a bottleneck so we may just keep it simple and stupid.
Best Regards, Zhang Boyang