Stack Exchange network consists of 183 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.
A colleague of mine found a counterexample (13 17 12 14 3 19 16 11 1 8 9 10 5 18 4 6 15 7 0 2) for k=2. Here, by always extending the first possible subsequence, we end up with 5 chains: (13 12 3 1 0, 17 14 11 8 5 4 2, 19 16 9 6, 10 7, 18 15). Let's pack the first, third, and fifth chains together to be (13 12 3 19 16 1 9 18 6 15 0) and then pack the second and fourth chains to (17 14 11 8 10 5 4 7 2). Keep in mind that here we want to merge the first with the second, and merge the third with the fourth, and leave the fifth as it was. It fails during "mergesort" at (17 14 13 12 11 8 *).
