title: Sorting strings in custom lexicographic order
body: <p>Sorting string array according to lexicographic order with a custom ordering (a permutation of <code>abcdefghijklmnopqrstuvwxyz</code>). This is the code:</p>
  
  <pre><code>/*
   * To change this license header, choose License Headers in Project Properties.
   * To change this template file, choose Tools | Templates
   * and open the template in the editor.
   */
  import java.io.BufferedReader;
  import java.io.InputStreamReader;
  import java.util.ArrayList;
  import java.util.Arrays;
  import java.util.List;
  
  /**
   *
   * @author sabertooth
   */
  public class SortString {
      /**
       * @param args the command line arguments
       */
      private static char[] index;
      private static BufferedReader br;
  
      public static void main(String[] args) throws Exception {
          // TODO code application logic here
          br = new BufferedReader(new InputStreamReader(System.in));
          int testCases = Integer.parseInt(br.readLine());
  
          for (int i = 0; i &lt; testCases; i++) {
              String dictionary = br.readLine();
  
              index = new char[dictionary.length()];
              index = dictionary.toCharArray();
  
              int set = Integer.parseInt(br.readLine());
  
              String[] unsortedInput = new String[set];
              String[] sortedInput = new String[set];
              for (int j = 0; j &lt; set; j++) {
                  unsortedInput[j] = br.readLine();
              }
  
              if (unsortedInput.length &lt;= 1) {
                  System.out.println(unsortedInput[0]);
              } else {
                  // merge sort on this array
                  sortedInput = mergeSort(unsortedInput);
                  for (int k = 0; k &lt; sortedInput.length; k++) {
                      System.out.println(sortedInput[k]);
                  }
              }
          }
      }
  
      private static String[] mergeSort(String[] unsortedInput) {
          if (unsortedInput.length &lt;= 1) {
              return unsortedInput;
          }
  
          String[] left;
          String[] right;
          int middle = unsortedInput.length / 2;
          if (unsortedInput.length % 2 == 0) {
              left = new String[middle];
              right = new String[middle];
          } else {
              left = new String[middle];
              right = new String[middle + 1];
          }
          System.arraycopy(unsortedInput, 0, left, 0, middle);
          System.arraycopy(unsortedInput, middle, right, 0, unsortedInput.length - middle);
  
          left = mergeSort(left);
          right = mergeSort(right);
          return merge(left, right);
      }
  
      private static String[] merge(String[] left, String[] right){
          List&lt;String&gt; leftList = new ArrayList&lt;String&gt;();
          List&lt;String&gt; rightList = new ArrayList&lt;String&gt;();
          List&lt;String&gt; result = new ArrayList&lt;String&gt;();
  
          leftList.addAll(Arrays.asList(left));
          rightList.addAll(Arrays.asList(right));
  
          while (leftList.size() &gt; 0 || rightList.size() &gt; 0) {
               if (leftList.size() &gt; 0 &amp;&amp; rightList.size() &gt; 0) {
                  // my own comparison
                  if (compare(leftList.get(0), rightList.get(0)) == -1) {
                      // leftString is less than right string
                      result.add(leftList.get(0));
                      leftList = leftList.subList(1, leftList.size());
                  } else
                  if (compare(leftList.get(0), rightList.get(0)) == 1) {
                      //left string is greater than right string
                      result.add(rightList.get(0));
                      rightList = rightList.subList(1, rightList.size());
                  } else
                  if (compare(leftList.get(0), rightList.get(0)) == 0) {
                      // leftString is equal to right string
                      result.add(leftList.get(0));
                      leftList = leftList.subList(1, leftList.size());
                  }
              } else
              if (leftList.size() &gt; 0) {
                  for (int i = 0; i &lt; leftList.size(); i++) {
                      result.add(leftList.get(i));
                  }
                  leftList.clear();
              } else
              if (rightList.size() &gt; 0) {
                  for (int i = 0; i &lt; rightList.size(); i++) {
                      result.add(rightList.get(i));
                  }
                  rightList.clear();
              }
          }
          String[] sortedInput = new String[result.size()];
          for (int i = 0; i &lt; result.size(); i++) {
              sortedInput[i] = result.get(i);
          }
          return sortedInput;
      }
  
      private static int compare(String leftString, String rightString) {
          // return -1 if left string is less than right string else left string is greater than right string return 1
  
          int min = Math.min(leftString.length(), rightString.length());
          int response = 0;
          for (int i = 0; i &lt; min; i++) {
              if (compareChar(leftString.charAt(i), rightString.charAt(i)) == -1) {
                  response = -1;
                  break;
              } else
              if (compareChar(leftString.charAt(i), rightString.charAt(i)) == 1) {
                  response = 1;
                  break;
              } else
              if (compareChar(leftString.charAt(i), rightString.charAt(i)) == 0) {
                  response = 0;
  
              }
          }
          return response;
      }
  
      private static int compareChar(char x, char y) {
          // returns true if x &lt; y
          int indexofx = 0;
          int indexofy = 0;
          int response = 0;
          for (int i = 0; i &lt; index.length; i++) {
              if (index[i] == x) {
                  indexofx = i;
              }
              if (index[i] == y) {
                  indexofy = i;
              }
          }
          if (indexofx &lt; indexofy) {
              response = -1;
          } else
          if (indexofx &gt; indexofy) {
              response = 1;
          } else
          if (indexofx == indexofy) {
              response = 0;
          }
          return response;
      }
  }
  </code></pre>
  
  <p>The problem is when I run this for some of the inputs the output is correct and for other the output is not correct. I have been debugging it but not able to find the bug.</p>
  
  <p><strong>EDITS</strong>:</p>
  
  <blockquote>
    <p>Adriana was playing with the English alphabet. When she was done playing with the alphabet, she realised that she had jumbled up the positions of the letters. Now, given a set of words, she wondered what would be the dictionary ordering of these words based on the new alphabet ordering which she made.</p>
    
    <p>In other words, given a permutation of the English alphabet, E and a set of words S, you need to output the lexicographical ordering of the words in the set S based on the new alphabet, E.</p>
    
    <p>Input:</p>
    
    <p>The first line will contain a single integer, T, denoting the number of test cases. T lines follow.</p>
    
    <p>For each test case: </p>
    
    <p>The first line will contain a string, E, the new alphabet ordering, which will be a permutation of <code>abcdefghijklmnopqrstuvwxyz</code></p>
    
    <p>The next line will contain a single integer M, the size of the set S. S lines follow, each containing a single word, containing lowercase latin characters.</p>
    
    <p>Output: for each test case, output S lines, each line containing one word from the set S, ordered lexicographically.</p>
    
    <p>Constraints</p>
  
  <pre><code>1 &lt;= T &lt;= 1000 
  1 &lt;= M &lt;= 100 
  1 &lt;= |W| &lt;= 50
  </code></pre>
    
    <p>Sample Input:</p>
  
  <pre><code>2
  abcdefghijklmnopqrstuvwxyz
  2
  aa
  bb
  bacdefghijklmnopqrstuvwxyz
  2
  aa
  bb
  </code></pre>
    
    <p>Sample Output:</p>
  
  <pre><code>aa
  bb
  bb
  aa
  </code></pre>
  </blockquote>