按嵌套的预先加载的关系(带分页)进行排序?

I am currently developing a system to filter and display data that is used via Eloquent and saved to the database in the following way:

Catalog -(1)---(n)-> Product -(1)---(n)-> Group -(n)---(n)-> Part
                     Product -(n)---(n)-> Provider

I'm eager loading these models completely and then display their attributes in my view as a table, the columns I base on user settings. Now I'm trying to add a way to order (and search through) these columns, but I can't seem to figure out any way to be able to order the whole result (Catalog is ultimately the 'master' collection) by any nested attributes.

For parts and providers (n:n relationships) I only need to be able to order the result by either the first or the last one's attributes.

Can anyone help me out here? I tried joins, but I can't figure out how to join both the first element and the last element for those two models and somehow distinguish them.