;with tblA(MENU_ID,UPPER_MENU_ID,MENU_NM,SORT_NO,UPPER_MENU_NM,SEQ,UPPER_SEQ,LEVL) As
(
      Select a.*
            ,Convert(varchar(max),'')
            ,Convert(Integer,1)
            ,Convert(Integer,ROW_NUMBER() Over (Order By a.MENU_NM Asc))
            ,1
        From TB_MENU a
       Where a.UPPER_MENU_ID = 0
      
   Union All     

      Select a.*
            ,Convert(varchar(max),b.MENU_NM)
            ,Convert(Integer,ROW_NUMBER() Over (Partition By b.MENU_NM Order By a.MENU_NM Asc))
            ,b.UPPER_SEQ
            ,b.LEVL + 1
        From TB_MENU a
                       Inner Join tblA b
                                         On a.UPPER_MENU_ID = b.MENU_ID
                                           
       Where a.UPPER_MENU_ID <> 0  
)
,tblB(MENU_ID,UPPER_MENU_ID,MENU_NM,SORT_NO,UPPER_MENU_NM,SEQ,UPPER_SEQ,LEVL,SERIAL) As
(
      Select a.*
            ,  Convert(varchar(max),a.UPPER_SEQ)
             + Replicate('1',a.LEVL-1)
             + Convert(varchar(max),a.SEQ)
       From tblA a
)
      Select a.*
        From tblB a
    Order By a.SERIAL ASC
 

WITH tb_menu(menu_id, upper_menu_id, menu_nm, sort_no) AS
(
          SELECT 1, 0, '메뉴 1'  , 10
UNION ALL SELECT 2, 1, '메뉴 1-1', 99
UNION ALL SELECT 3, 1, '메뉴 1-2', 99
UNION ALL SELECT 4, 0, '메뉴 3'  , 99
UNION ALL SELECT 5, 4, '메뉴 3-2', 99
UNION ALL SELECT 6, 4, '메뉴 3-1', 70
UNION ALL SELECT 7, 0, '메뉴 2'  , 50
)
, recursive_menu AS
(
SELECT menu_id, upper_menu_id, menu_nm, sort_no
     , 1 lv
     , CAST(RIGHT(CONCAT('0', sort_no), 2) AS VARCHAR) sort_str
  FROM tb_menu
 WHERE upper_menu_id = 0
 UNION ALL
SELECT c.menu_id, c.upper_menu_id, c.menu_nm, c.sort_no
     , p.lv + 1 lv
     , CAST(
       CONCAT(p.sort_str, RIGHT(CONCAT('0', c.sort_no), 2))
       AS VARCHAR) sort_str
  FROM recursive_menu p
 INNER JOIN tb_menu c
    ON p.menu_id = c.upper_menu_id
)
SELECT *
  FROM recursive_menu
 ORDER BY sort_str, menu_id
;

 -- 소트를 하나더 추가해 봤습니다...