I came up with several possible solutions, and am currently trying the last. What would you do?

1.

Walk through A and B simultaneously. If an integer in B exists in A then ignore it; if it doesn't exist then add it to the end of A.

At the end of this process, call Array.Sort on A (ie a QuickSort).

(Note that inserting a B element into A would surely take too long as it would involve moving all other A entries up.)

*Quite efficient but I am concerned at speed of final sort.*

2.

Create a new linked list with all the A entries.

Walk through the linked list and B simultaneously; for integers in B that need inserting, alter the linked list to add a new entry in the correct place.

At end, convert linked list back into an array.

*Not very efficient creating a linked list and converting back from linked list.*

3.

Walk through A and B simultaneously. Create a list structure where each element represents a block of integers in A or B, eg use integers 0-4 from A, integers 3-15 from B, integers 5-10 from A, etc.

At the end, create a new array from the list structure.

*This is a more complicated version of my final simpler solution.*

4.

Not quite sure if I thought this through properly.

Walk through A and B simultaneously. If the current integer in B is less than the current integer in A, then swap the two. This sounds simple but in fact the integer swapped into B will now possibly be out of order in B, so the element will need bubbling up until it finds its correct place.

At the end, simply add the remaining B elements to A.

*Superficially attractive but more complicated than it looks.*

5.

Walk through A and B simultaneously creating a new table C as you go.

*Simple*

Unless you can suggest otherwise...