Собственно решение. На оригинальность не претендую, работает только для двухуровневого меню:
//получаем список категорий из каталога
$items = $cataloAR->query("SELECT itemId, parentId,itemTitle FROM `catalog` ORDER BY parentId, itemId");
//сортируем предварительно по itemId, parentId
$ids = array();//массив для идентификаторов
$parents = array();//массив для родителей
// получаем список столбцов
foreach ($items as $key => $row) {
$ids[$key] = $row['itemId'];
$parents[$key] = $row['parentId'];
}
// сортируем по возрастанию id, по возрастанию parent
array_multisort($ids, SORT_ASC, $parents, SORT_ASC, $items);
//Создаем пустой массив для отсортированных данных типа - $entryList['itemId']['itemTitle']
$entryList = array();//пустой массив
$len = count($items); //получаем общее кол-во элементов для обработки
$currentEntry = 0; //номер текущего элемента
//итерируем
//пока не достигли последнего элемента в списке
while($currentEntry < $len){
//если нет текущего эл-то то переходим к следующему
if (!isset($items[$currentEntry])) {
$currentEntry++;
}
//берем текущий эл-т из $items
//кладем его в $entryList
$entryList[] = $items[$currentEntry];
// запоминаем текущий id
$currentId = $items[$currentEntry]['itemId'];
//убираем эл-т из $items, тк мы его уже положили в отсортированный список
unset($items[$currentEntry]);
//Ищем в $items записи с patternId = $items['itemId']
//ищем где такой-же родитель, кладем в отсортированный список
//удаляем эл-т который забрали
foreach ($items as $key => $value) {
if($value['parentId'] == $currentId){
$entryList[] = $value;
unset($items[$key]);
}
if (!isset($value)){
continue;
}
}
//увеличиваем счетчик
$currentEntry++;
}
//очищаем отсортированный массив от пустых эл-тов $entryList
$sortedList = array_filter($entryList);
//Enjoy it!
return $sortedList;
