<?php
/**
 * @file
 *   InsertionSort.php
 *
 * @author: marand
 *
 * @license General Public License version 2 or later
 */

namespace OSInet\Sort;

/**
 * Class InsertionSort
 *
 * @package OSInet\Sort
 *
 * @see http://en.wikipedia.org/wiki/Insertion_sort
 */
class InsertionSort extends Sort {

  public function sort($data, $comparison, $options = array()) {
    $sorted = array();
    foreach ($data as $unsorted_offset => $unsorted_value) {
      $found = false;
      foreach ($sorted as $sorted_offset => $sorted_value) {
        $result = $comparison($unsorted_value, $sorted_value);
        if ($result < 0) {
          $found = true;
          array_splice($sorted, $sorted_offset, 0, array($unsorted_value));
          break;
        }
      }
      if (!$found) {
        $sorted[] = $unsorted_value;
      }
    }

    return $sorted;
  }
}