title: How Do I Implement an Insertion Sort Method for A Generic ArrayList?
body: <p>I am meant to create a simple insertion sort method which sorts a series of generic names into alphabetical order. This should be simple, and I have already reviewed many other examples of insertion sort online, including on this site, yet I still cannot seem to obtain the correct output despite comparing my code, line-by-line, with other versions and being unable to identify what I have done different than some supposedly successful insertion sort methods.</p>
  <p>The following code is the main class which I am not meant to alter:</p>
  <pre><code>  public static void main(String[] args) {
      GenericTools t = new ToolBox();
      ArrayList&lt;String&gt; data = new ArrayList&lt;&gt;();
      data.add(&quot;Carlos&quot;);
      data.add(&quot;Alice&quot;);
      data.add(&quot;Bob&quot;);
      data.add(&quot;Zebra&quot;);
      data.add(&quot;Fred&quot;);
  
      t.insertionSort(data);
      data.forEach(x -&gt; System.out.println(x));
  }
  </code></pre>
  <p>And, this is the GenericTools interface referenced above, for the record:</p>
  <pre><code>public &lt;T&gt; void swap(ArrayList&lt;T&gt; data, int p1, int p2);
  </code></pre>
  <p>Finally, this is my code which should be correctly sorting this list:</p>
  <pre><code>@Override
      public &lt;T extends Comparable&lt;T&gt;&gt; void insertionSort(ArrayList&lt;T&gt; data) {
          int i, x =0;
          T key;
          for (i=1;i&lt;data.size();i++){
              key= data.get(i);
              while (x&gt;=0 &amp;&amp; data.get(x).compareTo(key) &gt; 0){
                  data.set(x+1,data.get(i));
                  x--;
              }
              data.set(x+1,key);
          }
        }
  
  </code></pre>
  <p>However, instead produces the following output:</p>
  <pre><code>Fred
  Alice
  Bob
  Zebra
  Fred
  </code></pre>
  <p>As opposed to correct output of:</p>
  <pre><code>Alice
  Bob
  Carlos
  Fred
  Zebra
  </code></pre>