<?php

class record {
    public $key;
    public $value;

    public function __construct($key, $value) {
        $this->key = $key;
        $this->value = $value;
    }
}

$records = array(1 => new record(1,1),
                 3 => new record(3,3),
                 4 => new record(4,4),
                 2 => new record(2,2),
                 );

//display
var_dump($records);

//loop through 1 - N
for ( $j = 2; $j <= count($records) ; $j++ ) {
    $i = $j - 1;
    $k = $records[$j]->key;
    $r = $records[$j];

    while ( $k >= $records[$i]->key ) {
        $records[$i + 1] = $records[$i];
        
        $i--;
        if ( $i <= 0 ) {
            break;
        }
    }

    $records[$i + 1] = $r;
 }

//display output
var_dump($records);