title: Keeping original indexes while sorting using Merge Sort in c
body: <p>I'm trying to sort a list with Merge Sort algoritm, while keeping it's original indices. I was told that the straight-forward solution was to use an array of indexes (obviously it would be initialized to 0 1 2 3...), and change it inside the merge-sort, as I change the corresponding values in the original array.
  The thing is, I can't find a way to make it work, because merge sort doesn't use the indexes of the original array, but rather the indexes of the small arrays that the original array splits into. I guess I'm missing something here... the solution I thought about so far was to treat the indexes array just as the original one, I mean split it into smaller arrays, declare a "helperIndexArray" for the new indexes, call merge with those variables etc... But it seems really unefficient. Isn't there a better way?
  I'd appreciate any tips, thanks!</p>
  
  <pre><code>void internalMsort(int array[], int size, int helperArray[], int index[]) {
      int left = size / 2, right = size - left;
      if (size &lt; 2)
          return;
      internalMsort(array, left, helperArray);
      internalMsort(array + left, right, helperArray);
      merge(array, left, array + left, right, helperArray, index);
      memCpy(array, helperArray, size);
  }
  
  void merge(int a[], int na, int b[], int nb, int c[], index[]) {
  int ia, ib, ic;
     for(ia = ib = ic = 0; (ia &lt; na) &amp;&amp; (ib &lt; nb); ic++)
       {
         if(a[ia] &lt; b[ib]) {
             c[ic] = a[ia];
             ia++;
             // here I was trying to swap index[ic] with index[ia] but it didn't work
         }
         else {
             c[ic] = b[ib];
             ib++;
         }
     }
     for(;ia &lt; na; ia++, ic++){ c[ic] = a[ia]; }
     for(;ib &lt; nb; ib++, ic++) { c[ic] = b[ib]; }
  }
  </code></pre>