The nav_menu_items are already sorted by menu_order.

When you go into the Appearance -> Menus and arrange the order menu the menu_order of each menu item gets updated.

To change the orderby parameter in the query that displays the menu you can use pre_get_posts to alter it. Example:

add_action( 'pre_get_posts', 'wpse_sort_nav' );
function wpse_sort_nav( $query ) {
        if ( $query->is_main_query() && get_query_var( 'post_type' ) == 'nav_menu_item' )
            $query->set( 'orderby', 'ID' );
    }

ID and menu_order are your only real options for sorting using the default post table. There is no title and the post_name is the same as the ID.

You could add additional parameters to the pre_get_posts filter using the meta data stored with each nav_menu_item.

Nav Menu metadata:

_menu_item_menu_item_parent
_menu_item_type
_menu_item_object_id
_menu_item_object
_menu_item_target
_menu_item_classes
_menu_item_xfn
_menu_item_url