title: Updating game records in Java
body: <p>We have game records organised as following:</p>
  
  <p><img src="https://i.stack.imgur.com/8KQkJ.png" alt="enter image description here"></p>
  
  <p>A player is allowed to play the game at different levels and a highscore table is kept to show the <strong>top 10 list of game records</strong>. Each game record on the highscore table contains a set of attributes, for example, the player's name, the total score obtained and the level from which the score was obtained. The list of game records is normally sorted from highest to the lowest score, indicating the rank of players from the highest to lowest level.</p>
  
  <p>We have to implement </p>
  
  <pre><code> public GameRecord[] updateGameRecords(GameRecord[] oldRecords, GameRecord newRecord)
  </code></pre>
  
  <p>in the following way:</p>
  
  <ol>
  <li>If there exists a record with same name and same level as newRecord then we update that record if the newRecord has a greater score and we then sort the oldRecords and return it.
  Otherwise, go to step 2</li>
  <li><p>If the number of records with the same level as that of newRecord are <strong>less than 10</strong>, then we insert the new record in oldRecords and sort it and then return it.Otherwise, go to step 3.</p></li>
  <li><p>If there is any record with poorer score at the same level as newRecord then we replace the record with lowest score of that level , since number of records for a given level cannot exceed 10 and then we sort and return oldRecords.</p></li>
  </ol>
  
  <p>This have so far been my code:</p>
  
  <pre><code>public GameRecord[] updateGameRecords(GameRecord[] oldRecords, GameRecord newRecord) {
      int index = -1, r = 0;
      boolean break_loop = false, same_name_level = false;
      for (int i = 0; i &lt; oldRecords.length; ++i) {
          while (i &lt; oldRecords.length &amp;&amp; newRecord.getLevel() &lt; oldRecords[i].getLevel()) {
              ++i;
              continue;
          }
          while (i &lt; oldRecords.length &amp;&amp; i &lt; oldRecords.length &amp;&amp; newRecord.getLevel() == oldRecords[i].getLevel()) {
              if (r == 0)
                  index = i;
              ++r;//r is number of records with same level
              if (!break_loop &amp;&amp; newRecord.getName().equals(oldRecords[i].getName())) {
                  same_name_level = true;
                  break_loop = true;
                  if (newRecord.getScore() &gt; oldRecords[i].getScore()) {
                      oldRecords[i].setScore(newRecord.getScore());
                  }
              }
              ++i;
          }
          if (break_loop == true)
              break;
      }
  
      if (break_loop == true) {
          Util.sort(oldRecords);
          return oldRecords;
      }
  
      if (r &gt; 0 &amp;&amp; r &lt; 10 &amp;&amp; same_name_level == false) {
          GameRecord[] temp = oldRecords.clone();
          oldRecords = new GameRecord[oldRecords.length + 1];
          System.arraycopy(temp, 0, oldRecords, 0, temp.length);
          oldRecords[temp.length] = newRecord;
          Util.sort(oldRecords);
          return oldRecords;
      }
  
      if (r == 10) {
          if (oldRecords[index + 9].getScore() &lt; newRecord.getScore())
              oldRecords[index + 9].setScore(newRecord.getScore());
          Util.sort(oldRecords);
          return oldRecords;
      }
  
      if (r == 0) {
          GameRecord[] temp = oldRecords.clone();
          oldRecords = new GameRecord[oldRecords.length + 1];
          System.arraycopy(temp, 0, oldRecords, 0, temp.length);
          oldRecords[temp.length] = newRecord;
          Util.sort(oldRecords);
          return oldRecords;
      } else
          return oldRecords;
  }
  </code></pre>
  
  <p>It is working fine but this is linear time complexity code that is it takes O( oldRecords.length ) + <strong>time taken by Util.sort()</strong> function which makes the total running time non-linear. </p>
  
  <p>Can you suggest me a linear time algorithm.</p>