(a)
L0[1] ... L0[n0], L1[1] ... L1[n1], ..., L(R-1)[1] ... L(R-1)[n(R-1)]

(b)
0         1       2      . . . . . . .     R-1
-         -       -                        ---
L0[1]   L1[1]   L2[1]                   L(R-1)[1]
L0[2]   L1[2]   L2[2]                   L(R-1)[2]
L0[3]   L1[3]   L2[3]                   L(R-1)[3] 
  .       .                                .
  .       .                                .
  .       .                                .
L0[n0]            .                    L(R-1)[n(R-1)]
        L1[n1]    .
                  .
                L2[n2]

Figure 1: Each section, L0, L1, L2, and so on, is already sorted. (a) Original list; (b) split into separate lists.

Back to Article
Copyright © 1999, Dr. Dobb's Journal