Библиотечная сортировка

function LibrarySort($arr) {
		
	global $arr_new;//Вспомогательный массив
		
	$e = 3;//Во сколько раз увеличиваем массив
	$rebalance_local = true;//Локальная (true) или полная (false) перебалансировка
	
	//Создаём вспомогательный массив
	$newSize = $e * (count($arr) + 1) - 1;
	$arr_new = array_fill(0, $newSize, null);
		
	//Первый элемент переносим в середину вспомогательного массива
	$arr_new[LibrarySort_Pos(1, 1, $newSize)] = $arr[0];
		
	//Начиная со второго элемента - ищем место вставки 
	//и переносим во вспомогательный массив
	$start = 0; $finish = $newSize - 1;	$i = 1;
	//Перебираем по порядку элементы основного массива
    while($i < count($arr)) {
		//Бинарным поиском ищем место вставки в дополнительном массиве
        $pos = LibrarySort_BinarySearch($arr[$i], $start, $finish, $newSize);
        if($pos === false) {//Точка вставки не обнаружена ни в каком виде
			//Полная перебалансировка вспомогательного массива
			LibrarySort_Rebalance_Total($i, $newSize);
		} else {//Точки вставки нашлась, но надо проверить, свободна ли она
			if($arr_new[$pos] !== null) {//Точка вставки занята
				if($rebalance_local) {//Локальная перебалансировка (+ вставка)
					LibrarySort_Rebalance_Local($arr[$i++], $pos, $newSize);
				} else {//Полная перебалансировка
					LibrarySort_Rebalance_Total($i, $newSize);
				}
			} else {//Нашли свободную точку вставки, просто вставляем
				$arr_new[$pos] = $arr[$i++];
			}
		}
	}
		
	//Переносим из дополнительного массива в основной
    $pos = 0;
    for($i = 0; $i <= $newSize - 1; $i++) {
        if($arr_new[$i] !== null) $arr[$pos++] = $arr_new[$i];
    }	
		
	return $arr;
}

//Позиция $number-го элемента из имеющихся $count
//во вспомогательном массиве после перебалансировки
//$number - какой по счёту в массиве (с начала) элемент
//$count - сколько на данный момент перенесено элементов
//$newSize - полный размер вспомогательного массива
//$number <= $count <= count($arr) <= $newSize)
function LibrarySort_Pos($number, $count, $newSize) {
	return $number * floor(($newSize + 1) / ($count + 1)) - 1;
}

//Бинарный поиск места вставки во вспомогательном массиве
//$search - значение элемента из основного массива, который нужно перенести во вспомогательный
//($start, $finish) - крайние индексы диапазона, в котором происходит поиск
//$newSize - полный размер вспомогательного массива
function LibrarySort_BinarySearch($search, $start, $finish, $newSize) {
	
	global $arr_new;//Вспомогательный массив

    //Сначала разберёмся с левой границей диапазона

    //На левой границе диапазона должен находиться элемент, а не пустая ячейка
    //Сужаем слева диапазон, если на левом краю пустые элементы
    while($arr_new[$start] === null && $start < $newSize - 1) {
        ++$start;
    }

    //Если на границе такого же значения элемент что и искомый,
	//то нужно вставить сразу за ним или перед ним
    if($search == $arr_new[$start]) {
        return LibrarySort_PosNearby($start, $newSize);
    //Может встретиться случай, когда искомый элемент меньше чем левая граница
    } elseif($search < $arr_new[$start]) {
        //Тогда искомому элементу место между левой 
		//границей и началом дополнительного массива
		if($start > 0) {//Перед $start есть свободное место
			$finish = $start;
			$start = 0;
			return floor(($start + $finish) / 2);
		} else {//$start == 0, перед ним ничего не вставить
			return $start;//Если не нашли пустую ячейку, возвращаем тогда непустую
		}
    }

    //На правой границе диапазона должен находиться элемент, а не пустая ячейка
    //Сужаем справа диапазон, если на левом краю пустые элементы
    while($arr_new[$finish] === null && $finish > 0) {
        --$finish;
    }

    //Если на границе такого же значения элемент что и искомый,
	//то нужно вставить сразу за ним или перед ним
    if($search == $arr_new[$finish]) {
        return LibrarySort_PosNearby($finish, $newSize);
    //Может встретиться случай, когда искомый элемент больше чем правая граница
    } elseif($search > $arr_new[$finish]) {
        //Тогда искомому элементу место между правой 
		//границей и концом дополнительного массива
		if($finish < $newSize - 1) {//После $finish есть свободное место
			$start = $finish;
			$finish = $newSize - 1;
			return ceil(($start + $finish) / 2);
		} else {//$finish == $newSize - 1, после него ничего не вставить
			return $finish;//Если не нашли пустую ячейку, возвращаем тогда непустую
		}
    }

	//Искомый элемент не совпадает с краями, 
	//значит, его нужно вставить где-то внутри диапазона
	//При этом нужно проверить, есть ли внутри диапазона ещё элементы
	If($finish - $start > 1) {//Делить диапазон имеет смысл, если там минимум 3 элемента
		$middle = ceil(($start + $finish) / 2); //Индекс середины диапазона
        $middle_Pos = 0; //Непустую "середину" диапазона пока не нашли
        $offset = 0; //Будем сдивгаться от точной середины в поисках непустого элемента

		//Итак, сдигаемся от середины влево/вправо, пока не обнаружим непустой элемент
        while($middle - $offset > $start && $middle_Pos == 0){
            if($arr_new[$middle - $offset] !== null) {
                $middle_Pos = $middle - $offset;
            } elseif($middle + $offset < $finish &&  $arr_new[$middle + $offset] !== null) {
                $middle_Pos = $middle + $offset;
            }
            ++$offset;
        }
	
        //Если внутри нашли непустой элемент, то, в зависимости от его значения, 
		//или ищем место возле него или рекурсивно применяем к левой или правой части диапазона
        If($middle_Pos) {
            if($arr_new[$middle_Pos] == $search) {
				return LibrarySort_PosNearby($middle_Pos, $newSize);
            } else {
				if($arr_new[$middle_Pos] > $search) {
					$finish = $middle_Pos;
				} else {//$arr_new[$middle_Pos] < $search
					$start = $middle_Pos;
				}
                return LibrarySort_BinarySearch($search, $start, $finish, $newSize);
            }
        } else {//$middle_Pos == 0 - внутри диапазона (не считая его границ) не найдены непустые элементы
            return $middle;//Середина такого диапазона - место, куда можно вставить элемент
        }

    } else {//Нашли минимальный отрезок, но свободного места в нём нет
		return floor(($start + $finish) / 2);
	}
	
	return false;//Если сюда добрались, значит бинарный поиск ничего не дал

}

//Если элемент равен концу отрезка, то ставим его рядом слева или справа
//$start - позиция, на которой уже стоит элемент равный искомому
//$newSize - полный размер вспомогательного массива
function LibrarySort_PosNearby($start, $newSize) {
	global $arr_new;//Вспомогательный массив
    //Сначала попытаемся найти свободное место перед элементом
    for($left = $start - 1; $left >= 0; $left--) {
        if($arr_new[$left] === null) {//Пустая ячейка
            return $left;//Сюда и вставим
        } elseif($arr_new[$left] <> $arr_new[$start]) {//Встретился элемент с другим значением
            break; //Слева ничего не поставишь, можно дальше влево не искать
        }
    }
	//Если не нашли свободного места слева, попробуем поискать справа
	for($right = $start + 1; $right <= $newSize - 1; $right++) {
        if($arr_new[$right] === null) {//Пустая ячейка
            return $right; //Сюда и вставим
        } elseif($arr_new[$right] <> $arr_new[$start]) {//Встретился элемент с другим значением
            break; //Справа ничего не поставишь, можно дальше вправо не искать
		}
    }
	return $start; //Ни слева ни справа от конца отрезка не нашли места вставки. Но мы возвращаем хотя бы точку, с которой начали поиск
}

//Местная перебалансировка вспомогательного массива
//$insert - значение, которое надо вставить
//$pos - начиная с какого элемента нужно сдвинуть несколько штук влево или вправо
//$newSize - полный размер вспомогательного массива
function LibrarySort_Rebalance_Local($insert, $pos, $newSize) {
	global $arr_new;//Вспомогательный массива
	//Уточняем $pos для $insert, иногда надо чуть левее или правее
	while($pos - 1 >= 0 && $arr_new[$pos - 1] !== null && $arr_new[$pos - 1] > $insert) {--$pos;}
	while($pos + 1 <= $newSize - 1 && $arr_new[$pos + 1] !== null && $arr_new[$pos + 1] < $insert) {++$pos;}
	$middle = (integer) $newSize / 2;//Середина массива
	if($pos <= $middle) {//Точка вставки в левой части массива
		if($arr_new[$pos] !== null && $arr_new[$pos] < $insert) ++$pos;
		//Сдвигаем вправо
		$right = $pos;
		while($arr_new[++$right] !== null) {}
		for($i = $right; $i > $pos; $i--) {
			$arr_new[$i] = $arr_new[$i - 1];
		}
	} else {//Точка вставки в правой части массива	
		if($arr_new[$pos] !== null && $insert < $arr_new[$pos]) --$pos;
		//Сдвигаем влево
		$left = $pos;
		while($arr_new[--$left] !== null) {}
		for($i = $left; $i < $pos; $i++) {
			$arr_new[$i] = $arr_new[$i + 1];
		}		
	}
	$arr_new[$pos] = $insert;
}

//Полная перебалансировка вспомогательного массива
//$count - сколько элементов на данный момент в массиве
//$newSize - полный размер вспомогательного массива
function LibrarySort_Rebalance_Total($count, $newSize) {
    
	global $arr_new;//Вспомогательный массив
	global $library_Number;//Какой по счёту элемент переносим
	global $library_LeftPos;//Самая левая позиция при которой влево переносили элементы
	
    $library_Number = $count; //Начинаем переносить последние с конца по счёту элементы
    $library_LeftPos = $newSize - 1;//Пока неизвестна, поэтому максимально правое значение
        
    //Проходим элементы в дополнительном массиве от последнего к началу
    $i = $newSize - 1;
    while($i >= 0) {
        if($arr_new[$i] !== null) {//Очередной непустой элемент
			$pos = LibrarySort_Pos($library_Number, $count, $newSize);//Его надо перенести сюдаnewSize=$newSize");
            if($i == $pos) {//Элемент уже стоит на своём месте
                --$i;//Переходим дальше влево по дополнительному массиву
			} elseif($i < $pos) {//Элемент нужно перенести вправо
				$arr_new[$pos] = $arr_new[$i];
				$arr_new[$i] = null;
				--$i;//Переходим дальше влево по дополнительному массиву
            } else {//$i > $pos - элемент нужно перенести влево
                //Рекурсивная процедура для переноса элемента влево
                LibrarySort_RemoveLeft($i, $pos, $count, $newSize);
				$i = ($i > $library_LeftPos) ? $library_LeftPos - 1 : --$i;
			}
			--$library_Number;//Переносимых элементов стало на одного меньше
		} else {//Пустая клетка, нечего переносить
			--$i;//Переходим дальше влево по дополнительному массиву
		}
    }    
}

//Перенос элемента левее в перебалансируемом массиве. 
//Этому могут мешать другие элементы, находящиеся слева
//$i - в какой ячейке находится элемент, который нужно перенести
//$pos - в какую ячейку нужно перенести элемент
//$count - сколько всего сейчас элементов во вспомогательном массиве
//$newSize - полный размер вспомогательного массива
function LibrarySort_RemoveLeft($i, $pos, $count, $newSize) {

	global $arr_new;//Вспомогательный массив
	global $library_Number;//Какой по счёту элемент переносим
	global $library_LeftPos;//Самая левая позиция при которой влево переносили элементы
	
    $left = false; $left_Pos = false;//Пока ближайший сосед слева не найден
    $j = $i;//Начинаем перебирать сразу от переносимого элемента
    //Нужно выяснить ближайшего соседа слева
    while($j > 0 && $left === false) {//Пока в пределах вспомогательного массива и пока не найден ближайший сосед слева
        --$j; //Продолжаем влево поиск ближайшего соседа
        if($arr_new[$j] !== null) $left = $j;//Ближайший сосед слева обнаружен
    }
    if($left === false || $left < $pos) {//Ближайший сосед слева (если он найден) не мешает переносу
        //Ничего дополнительно предпринимать не нужно
    } else { //$left >= $pos, сосед слева мешает переносу
        --$library_Number;//Значит, левее нужно перенести мешающего соседа слева
        $left_Pos = LibrarySort_Pos($library_Number, $count, $newSize);//Соседа слева надо перенести сюда
        //Рекурсивно переносим соседа слева на его правильную позицию
        LibrarySort_RemoveLeft($left, $left_Pos, $count, $newSize);
        //Сосед слева отодвинут, теперь можно перенести элемент
    }
	//С соседом слева всё нормально, переносим элемент
	$arr_new[$pos] = $arr_new[$i];
	$arr_new[$i] = null;
    //Уточняем, был ли это самый влево перенесённый из соседей
    if($pos < $library_LeftPos) $library_LeftPos = $pos;
}