Hi,
perhaps I'm missing something here, but this looks like a simple case of "nup", and is the default operation for pdfnup when run without options. Eg
Code:
pdfnup infile.pdf outfile.pdf
In Debian pdfnup is in the texlive-extra-utils package, so it is probably the same in Ubuntu.
HTH,
Evo2.