search

kaist-cp / cs500

Moved to https://cp-git.kaist.ac.kr/jeehoon.kang/cs500
25 stars 7 forks source link

Odd-even Merge Sort when n=1 #69

Closed jaeseok-huh closed 5 years ago

jaeseok-huh commented 5 years ago

(For the future readers, I'm looking at commit 6285bfa) When n=1, in the Algorithm 3.2 Odd-Even Merge Sort, it is not clear how the function call works. Line 4, 5 should be ignored because the lengths of the arguments are less than 2. Then the resulting sequence (line 8) is not correct. A counterexample is shown below.

A=(2,5), B=(1,6)   (n=1)
Line 8 yields (2, 1, 5, 6)

Could someone help me out?

cyron1259 commented 5 years ago

Issue #62 solves your problem, although this ruins the even length assumption.