The first question is what exactly do they mean by A5 format? They might mean each page is A5, they might want a pair of A5 pages side by side on an A4, they might even mean they want all the pages sorted in the right order so that for example the first and last page are side by side, then page and and the last-but-one, etc.

Whichever they mean, there are free solutions, but we'd better not begin down the wrong path.