php 2d array sort parent child -

yes,yes know, here bunch of questions array sorting, need 1 more specific explanation.
have db table store multi-level menu products.
like: itemid, parentid, itemtitle, ...
use table build menu on webpage, using reccursive function , want use db-table data backend html form, option list. unsorted data db need sort correctly , put in json array. half part of work done this:

//empty arrays sorting purposes   $ids = array(); $parents = array(); // iterate, $items - unsorted array db  foreach ($items $key => $row) {     $ids[$key]  = $row['itemid'];     $parents[$key] = $row['parentid']; } // sorting array_multisort($ids, sort_asc, $parents, sort_asc, $items); //now $items partly sorted 

fig.1
$items list looks like:
(itemid - parentid - itemtitle)
1 - 0 - ***a
2 - 0 - ***b
3 - 0 - ***c
4 - 0 - ***d
6 - 1 - ***e
7 - 1 - ***f
8 - 1 - ***g
9 - 2 - ***h
10 - 2 - ***i
11 - 2 - ***j
12 - 2 - ***k
13 - 2 - ***l
14 - 3 - ***m
15 - 3 - ***n
16 - 3 - ***o
17 - 4 - ***p
18 - 4 - ***q

fig.2
need:
1 - 0 - ***a
6 - 1 - ***e
7 - 1 - ***f
8 - 1 - ***g
2 - 0 - ***b
9 - 2 - ***h
10 - 2 - ***i
11 - 2 - ***j
12 - 2 - ***k
13 - 2 - ***l
3 - 0 - ***c
14 - 3 - ***m
15 - 3 - ***n
16 - 3 - ***o
4 - 0 - ***d
17 - 4 - ***p
18 - 4 - ***q

so question - how convert array fig.1 array fig.2 neat way?

so soution. 2-level menu only:

    //get categories, primary sorted mysql     $items = $cataloar->query("select itemid, parentid,itemtitle `catalog` order parentid, itemid");  //pre-sort - itemid, parentid     $ids = array();//array id`s     $parents = array();//array parents // columns list     foreach ($items $key => $row) {         $ids[$key]  = $row['itemid'];         $parents[$key] = $row['parentid'];     } // sort ascending id, ascending parent     array_multisort($ids, sort_asc, $parents, sort_asc, $items); //make emptyarray sorteddata, - $entrylist['itemid']['itemtitle']      $entrylist = array();//empty array     $len = count($items); //count elements proceeding     $currententry = 0;  //current element number,start 0-element //iterate //while reaching last element in list    while($currententry < $len){         //if current element empty => go next element         if (!isset($items[$currententry])) {             $currententry++;         }   //get current element $items //put $entrylist         $entrylist[] = $items[$currententry];     // current id          $currentid = $items[$currententry]['itemid'];         //remove element  $items, because put sorted list         unset($items[$currententry]);      //search in $items entries  patternid = $items['itemid']   //put sorted list //remove element          foreach ($items $key => $value) {             if($value['parentid'] == $currentid){                 $entrylist[] = $value;                                unset($items[$key]);                               }              if (!isset($value)){                 continue;             }          }  //increase counter                            $currententry++;                        }     //purge sorted list empty elements  $entrylist     $sortedlist = array_filter($entrylist);  //enjoy it!     return $sortedlist; 

i made assumptions array , created below code. able replicate desired output creating 2 new arrays ($root , $menu), , looping through each of them build menu. tricky, , best answer build array differently beginning, if that's not possible, code should need be:

$items[] = array('itemid' => 1,'parentid' => 0,'itemtitle' => '***a'); $items[] = array('itemid' => 2,'parentid' => 0,'itemtitle' => '***b'); $items[] = array('itemid' => 3,'parentid' => 0,'itemtitle' => '***c'); $items[] = array('itemid' => 4,'parentid' => 0,'itemtitle' => '***d'); $items[] = array('itemid' => 6,'parentid' => 1,'itemtitle' => '***e'); $items[] = array('itemid' => 7,'parentid' => 1,'itemtitle' => '***f'); $items[] = array('itemid' => 8,'parentid' => 1,'itemtitle' => '***g'); $items[] = array('itemid' => 9,'parentid' => 2,'itemtitle' => '***h'); $items[] = array('itemid' => 10,'parentid' => 2,'itemtitle' => '***i'); $items[] = array('itemid' => 11,'parentid' => 2,'itemtitle' => '***j'); $items[] = array('itemid' => 12,'parentid' => 2,'itemtitle' => '***k'); $items[] = array('itemid' => 13,'parentid' => 2,'itemtitle' => '***l'); $items[] = array('itemid' => 14,'parentid' => 3,'itemtitle' => '***m'); $items[] = array('itemid' => 15,'parentid' => 3,'itemtitle' => '***n'); $items[] = array('itemid' => 16,'parentid' => 3,'itemtitle' => '***o'); $items[] = array('itemid' => 17,'parentid' => 4,'itemtitle' => '***p'); $items[] = array('itemid' => 18,'parentid' => 4,'itemtitle' => '***q');  foreach ($items $itemarray) {     $parent = $itemarray['parentid'];     $item = $itemarray['itemid'];     $title = $itemarray['itemtitle'];      if ($parent == 0) {         // root item         $root[$item] = $title;     } else {         // submenu item         $menu[$parent][$item] = $title;     } }  foreach ($root $key => $value) {     // root item, 0.     echo "$key, 0, $value <br/>";     foreach ($menu $parent => $item) {         if ($parent == $key) {             foreach ($item $itemid => $title) {                 // output submenu items under root                 echo "$itemid, $parent, $title <br />";             }         }     } }