title: Keeping two arrays, String[] and int[], parallel with merge sort
body: <p>I'm having trouble with keeping two arrays in parallel within my Merge Sorting algorithm.
  Suppose I have array defMergeSort and intMergeSort2.</p>
  
  <p>I would like to lexicographically order String defMergeSort,</p>
  
  <pre><code>String[] defMergeSort = {"Echo", "Alpha", "Charlie", "Beta", "Alpha", "Echo"};
  </code></pre>
  
  <p>Array intMergeSort2 represents the element position in parallel to defMergeSort. (Ex: defMergeSort[0] = Echo contingent to intMergeSort2[0] = 0, defMergeSort[3] = Beta contingent to intMergeSort2[3] = 3)
  intMergeSort2 is to be rearranged in parallel to defMergeSort, although not numerically sorted,</p>
  
  <pre><code>int[] intMergeSort2 = {0,1,2,3,4,5};
  </code></pre>
  
  <p>The end result should look similar to this (Not sure if parallel ordering for intMergeSort2[] in my example is correct for duplicate Strings in defMergeSort[]):</p>
  
  <ul>
  <li>defMergeSort[0] Alpha =   intMergeSort2[1] 1</li>
  <li>defMergeSort[1] Alpha =   intMergeSort2[4] 4</li>
  <li>defMergeSort[2] Beta =    intMergeSort2[3] 3</li>
  <li>defMergeSort[3] Charlie = intMergeSort2[2] 2</li>
  <li>defMergeSort[4] Echo =    intMergeSort2[0] 0</li>
  <li>defMergeSort[5] Echo =    intMergeSort2[5] 5</li>
  </ul>
  
  <p>The following merge sort algorithm can lexicographically order defMergeSort, although I cannot figure out how to keep defMergeSort in parallel as stipulated above:</p>
  
  <pre><code>//mergeSort code found at:
  //http://www.buildingjavaprograms.com/code-files/2ed/ch13/MergeSort.java
  public static void mergeSort(String[] defMergeSort, int[] intMergeSort2) {
      if (defMergeSort.length &gt; 1) {
          // split array into two halves
          String[] left = leftHalf(defMergeSort);
          String[] right = rightHalf(defMergeSort);
          // recursively sort the two halves
          mergeSort(left, intMergeSort2);
          mergeSort(right, intMergeSort2);
          // merge the sorted halves into a sorted whole
          merge(defMergeSort, intMergeSort2, left, right);
      }
  }
  
  // Returns the first half of the given array.
  public static String[] leftHalf(String[] defMergeSort) {
      int size1 = defMergeSort.length / 2;
      String[] left = new String[size1];
      for (int i = 0; i &lt; size1; i++) {
          left[i] = defMergeSort[i];
      }
      return left;
  }
  
  // Returns the second half of the given array.
  public static String[] rightHalf(String[] defMergeSort) {
      int size1 = defMergeSort.length / 2;
      int size2 = defMergeSort.length - size1;
      String[] right = new String[size2];
      for (int i = 0; i &lt; size2; i++) {
          right[i] = defMergeSort[i + size1];
      }
      return right;
  }
  
  // Merges the given left and right arrays into the given
  // result array.  Second, working version.
  // pre : result is empty; left/right are sorted
  // post: result contains result of merging sorted lists;
  public static void merge(String[] defMergeSort, int[] intMergeSort2,
  String[] left, String[] right){
      int i1 = 0;   // index into left array
      int i2 = 0;   // index into right array
      for(int i = 0; i &lt; defMergeSort.length; i++){
          if (i2 &gt;= right.length || (i1 &lt; left.length &amp;&amp;
          left[i1].compareTo(right[i2]) &lt;= 0)) {
              defMergeSort[i] = left[i1];
              i1++;
          } else {
              defMergeSort[i] = right[i2];
              i2++;
          }
      }
  }
  </code></pre>