title: How to insert an integer into a sorted List in Java?
body: <p>I would like to write a function insertAndSort() that will take as parameter an Integer "num" and a List of integers "list". Let's assume the List lust is already sorted.</p>
  
  <p>The algorithm is supposed to work this way :</p>
  
  <ol>
  <li>Add "num" to L and keep the List sorted after "num" has been added.</li>
  <li>Return the sorted List.</li>
  </ol>
  
  <p>WARNING : We do not know whether the list is sorted ASC or DESC. And that is precisely my problem !</p>
  
  <p>Example :</p>
  
  <ul>
  <li>if "num" = 4 and L = {1, 3, 5, 7}, then the final sorted List is {1, 3, 4, 5, 7}</li>
  <li>if "num" = 4 and L = {7, 5, 3, 1}, then the final sorted List is {7, 5, 4, 3, 1}</li>
  <li>I can not use sorting API such as Collections.sort or Collections.reverseOrder etc...</li>
  </ul>
  
  <p>So far, I've produced this code :</p>
  
  <pre><code>public static void main(String[] args) {
  
      int num = 4;
      List&lt;Integer&gt; myList = Arrays.asList(1, 3, 5, 7);
      List&lt;Integer&gt; newList = new ArrayList&lt;Integer&gt;();
      newList = insertAndSort(myList, num);
      System.out.println(newList);
  
  }
  
  public static List&lt;Integer&gt; insertAndSort(List&lt;Integer&gt; list, int num) {
          List&lt;Integer&gt; listSecond = new ArrayList&lt;Integer&gt;(list.size()+1);
          for(int i = 0; i &lt;= list.size() ; i++) {
              if(num &lt; list.get(i)) {
                  if(!listSecond.contains(num)){
                      listSecond.add(num);
                  } else {
                      listSecond.add(list.get(i-1));
                      listSecond.add(list.get(i));
                      break;
                  }            
              } else {
                  listSecond.add(list.get(i));
              }
          }
          return listSecond;
      } 
  </code></pre>
  
  <p>The problem is that this seems to be working with a single type of List: the ascending one.
  When I take a sorted descending List, it does not work anymore.</p>
  
  <p>Do you have any idea to make this work with both type of List ?</p>
  
  <p>Thanks and Regards.</p>