Library sorting

functionLibrarySort($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)functionLibrarySort_Pos($number, $count, $newSize){
	return $number * floor(($newSize + 1) / ($count + 1)) - 1;
}

//Бинарный поиск места вставки во вспомогательном массиве//$search - значение элемента из основного массива, который нужно перенести во вспомогательный//($start, $finish) - крайние индексы диапазона, в котором происходит поиск//$newSize - полный размер вспомогательного массиваfunctionLibrarySort_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);
	}
	returnfalse;//Если сюда добрались, значит бинарный поиск ничего не дал
}

//Если элемент равен концу отрезка, то ставим его рядом слева или справа//$start - позиция, на которой уже стоит элемент равный искомому//$newSize - полный размер вспомогательного массиваfunctionLibrarySort_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 - полный размер вспомогательного массиваfunctionLibrarySort_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 - полный размер вспомогательного массиваfunctionLibrarySort_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 - полный размер вспомогательного массиваfunctionLibrarySort_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;
}