c - storing original index in an array

Question

I am trying to perform a mergesort without actually rearranging the array. Let me explain a little better. Say I have an array:

3
5
6
7
0
4
1
2

If 5 (currently at index 1) gets moved to index 6 for example I need my program to remember the index of where 5 was originally stored. How can I remember the original index?

Answer 1

Make a parallel array of pointers to the original array. Sort the pointers, not the originals. Your index positions remain unchanged, and you now have a sorted "view" of the array.

Answer 2

What you can do is use a structure for every element, and make an array of those structure objects. For example-

typedef struct
{
  int val;
  int index;
}element;

Loop through the array, fill the val field with the value and the other with the original position.

When sorting, you compare on the val field, and leave the index intact. So now you have the original position, and the array can also be sorted.