Talk:Sort-merge join

This is a truly horrible description of a sort-merge join. Both the lay reader and the expert reader will be left flummoxed. Even pseudo code would be better than the Pascal-ish gobble-dee-gook here.

The algorithm as given appears wrong to me. E.g. if the input was lists of size 1 containing the same key (e.g. List 1: [a:"foo"], List 2: [a:"foo"] this would not produce the desired output. The while loop would never execute, since the "advance" function would leave both sorted lists empty. —Preceding unsigned comment added by 194.110.194.1 (talk) 12:25, 13 May 2008 (UTC)[reply]

Where the matching tuples are combined ? i see only adding the left tuple in the result.--213.140.16.187 (talk) 15:27, 22 June 2008 (UTC)[reply]

Algorithm as described here is clearly incorrect. I'm amazed that this garbage shows in the first place in Google search for sorted merge. —Preceding unsigned comment added by 91.77.81.233 (talk) 06:11, 21 June 2009 (UTC)[reply]

Bug in pseudocode and implementation[edit]

This looks wrong for the case where either the left or right set has multiple matches for any single row in the other set. Given simple result set Left(A,B,C,D) Right(B, C, C, D, E) This code would give (B, C, D) while the correct result is (B, C, C, D)

Sort bound[edit]

The actual number of I/O's to sort P pages is better than O(P log P). If you have M pages of memory, to use as buffer, it's O(P log_M P) which is a reduction by a factor of log M.

See the Wikipedia article on external sorting. 12.27.17.2 (talk) 17:01, 24 February 2023 (UTC)[reply]