How to sort through two merged collections that have different models

I have two models Cities and States. One City has 1 State and one State can have 0 or more Cities. I need to retrieve all Cities and States separately because I need to display states even if no a state has no related cities (like Alabama in the below example). The issue is I need to sort by State name first, and than by Cities in that state (if there are any)

Cities

id, state_id, name 
1, 1, San Diego 
2, 1, Hollywood
3, 2, Seattle
4, 3, Pheonix

States

id, name
1, California
2, Washington 
3, Arizona
4, Alabama 

Controller

$cities = Cities::with('state')->get(); // Returns the state relationship 
$states = States::get();

$merged = $states->merge($cities);

I would now like to sort by State name first, and than all the cities in that State and return a merged collection similar to this

{
    id: 4,
    name: Alabama,
}, 
{
    id: 3,
    name: Arizona,
}, 
{
    id: 3,
    name: Pheonix,
    state_id: 3
    state: {
        id: 3,
        name: Arizona
    }
},
{
    id: 1,
    name: California
},
{
    id: 2,
    name: Hollywood
    state_id: 1,
    state: {
        id: 1,
        name: California
    }
},
{
    id: 1,
    name: San Diego,
    state_id: 1,
    state: {
        id: 1,
        name: California
    }
}, 
{
    id: 2,
    name: Washington,

},
{
    id: 2,
    name: Seattle,
    state_id: 2,
    state: {
        id: 2,
        name: Washington
    }
}

via Chebli Mohamed