@OP - we've (other moderators and I) been playing around with different ways to solve this problem but I think I'll share my strategy with you because it's pretty straightforward, in my opinion. Of course, I'm biased but oh well. Anyway, here's how I approached it.
The approach is kind of like a modified
selection sort except we're using the second array to determine the ordering of elements instead of their natural ordering (1, 2, 3, 4, etc.). I call that array the
order. I refer to the array we want to reorder simply as
numbers.
Using your data,
numbers = {2, 3, 1, 3, 2, 4, 6, 7, 9, 2, 19} and
order = {2, 1, 4, 3, 9, 6}
I need to keep track of the numbers that are already in the desired order. I'll use
sorted to represent the index where I want to put the next number we want to put in proper order. Initially, that index will be 0.
{2, 3, 1, 3, 2, 4, 6, 7, 9, 2, 19}
↑
sorted = 0
For each element,
n, in the
order array, I'll do this:
Starting from
sorted, iterate over the rest of
numbers:
if the current element in
numbers is equal to
n then I'll move that value down to the spot pointed to by
sorted and shift every number in between up.
That's pretty much it. Let's see how it works with your data.
So iterating over
order, the first value of
n will be 2. This means I'm going to find all the elements in
numbers equal to 2 and rotate them to where
sorted currently points to and then shifting everything in between towards the end of
numbers. The first 2 is already in place, so no shifting is done but still we increment
sorted to 1 because that's the next spot that we'll be moving a reordered number into.
{2, 3, 1, 3, 2, 4, 6, 7, 9, 2, 19}
↑
sorted = 1
Continuing our search for
n (2) in
numbers, we find another in
numbers[4]
numbers[4]
↓
{2, 3, 1, 3, 2, 4, 6, 7, 9, 2, 19}
↑
sorted = 1
We need to move it to where
sorted is pointing and shift all those numbers in between to the right:
→ → →
{2, 2, 3, 1, 3, 4, 6, 7, 9, 2, 19}
↖ ← ← ← ⤶
↑
sorted = 1
We increment
sorted again and now it's 2. We look for another element in
numbers that's equal to
n (2). We find another in
numbers[9].
numbers[9]
↓
{2, 2, 3, 1, 3, 4, 6, 7, 9, 2, 19}
↑
sorted = 2
We rotate that 2 down to where
sorted is pointing and shift everything in between to the right.
→ → → → → → →
{2, 2, 2, 3, 1, 3, 4, 6, 7, 9, 19}
↖ ← ← ← ← ← ← ← ← ← ⤶
↑
sorted = 2
Once again, we increment
sorted to 3. (We basically increment
sorted each time we move a number down to that spot in
numbers)
Since there are no more 2s in
numbers to move, we get the next number in the
order array:
{2, 1, 4, 3, 9, 6}. So,
n is now 1.
Starting from where
sorted currently points, we scan
numbers for
n (1). We find it in
numbers[4].
numbers[4]
↓
{2, 2, 2, 3, 1, 3, 4, 6, 7, 9, 19}
↑
sorted = 3
We move 1 and shift the number(s) in between to the right.
→
{2, 2, 2, 1, 3, 3, 4, 6, 7, 9, 19}
↖⤶
↑
sorted = 3
We increment
sorted to 4 and find no other one. So we get the next
n from
order:
{2, 1, 4, 3, 9, 6}.
n is now 4.
numbers[6]
↓
{2, 2, 2, 1, 3, 3, 4, 6, 7, 9, 19}
↑
sorted = 4
Move and shift right:
→ →
{2, 2, 2, 1, 4, 3, 3, 6, 7, 9, 19}
↖ ← ⤶
↑
sorted = 4
We increment
sorted to 5, and get the next number to find from
order:
{2, 1, 4, 3, 9, 6}.
n is now 3. We find that all the 3s are already in place but we still follow the same procedure and increment
sorted for each 3 we find that's already in place.
{2, 2, 2, 1, 4, 3, 3, 6, 7, 9, 19}
↑
sorted = 5
{2, 2, 2, 1, 4, 3, 3, 6, 7, 9, 19}
↑
sorted = 6
{2, 2, 2, 1, 4, 3, 3, 6, 7, 9, 19}
↑
sorted = 7
n == 9
↓
{2, 2, 2, 1, 4, 3, 3, 6, 7, 9, 19}
↑
sorted = 7
→ →
{2, 2, 2, 1, 4, 3, 3, 9, 6, 7, 19}
↖ ← ⤶
↑
sorted = 7
{2, 2, 2, 1, 4, 3, 3, 9, 6, 7, 19}
↑
sorted = 8, n = 6
{2, 2, 2, 1, 4, 3, 3, 9, 6, 7, 19}
↑
sorted = 9, n = 6
That's the last n from order[]!
We're DONE!
{2, 2, 2, 1, 4, 3, 3, 9, 6, 7, 19} -- the rightmost are missing from order
↑
|⟸ . . ordered . . ⟹| sorted
Since we just shift numbers that are not sorted to the right, we maintain their original order relative to each other. When we run out of numbers in
order, then everything in
numbers before the
sorted index will be arranged in the proper order and everything from
sorted onwards will be the values in
numbers that are missing from
order, in their original order.
Pretty neat, right?