alternative to insertion sort + copy when small array must be sorted *and* copied

Question

Consider two arrays, A and B, both of length N, with N fairly small. I'd like to sort the elements in A and store the sorted elements in B.

It would be fairly straightforward to do an in-place insertion sort on A and then bulk-copy the sorted values to B. However, this fails to take advantage of two things:

1. there is scratch space of size N available for use and
2. the sorted values need to eventually end up in B and not A.

Can anyone suggest different approach (possibly a modified insertion sort?) that would take advantage of one (or both) of those and end up outperforming the simple solution of insertion sort + copy?

Answer 1

Coming in many years later, but if someone else chances upon this, here's my two cents. Using a combination of insertion sort with a fast out of place sort like merge sort might provide some minimal improvements.

1. Split the array into quarters and sort using insertion sort
2. Merge first and second quarters onto scratch space, same for 3rd and 4th quarters
3. Merge first half and second half from scratch into your target array

Again, this probably provides minimal real world improvement and is probably a case of premature optimization. You would be better off benchmarking your application to see if you really need an improvement in this part of your algorithm or if your time is better spent optimizing something else.