Ordering versioned Projects with pagination

I am having some struggles with a combination of factors that work nice individualy, but together it starts causing me some headaches:

• I have Project models which have a OneToMany relation to different ProjectVersions which store the actual project data (title, description etc), and each time this data is altered a new version is stored so I can display the change history of a project. The Project model also has a OneToOne relation to the latest_version, which returns the ProjectVersion with the highest version number. This allows me to eager load this information and display the current title of the project in overviews:

public function versions()
{
    return $this->hasMany('App\ProjectVersion');
}
public function latest_version()
{
    return $this->hasOne('App\ProjectVersion')
            ->orderBy('version', 'desc');
}

• I use Laravel's pagination implementation to display all projects in an overview. I combine this with whereHas methods to allow some filtering by Category and search queries from user input:

$projects = Project::whereHas('versions', function ($query) {
            $query->where('title', 'LIKE', "%" . Input::get('search') . "%");
})->whereHas('categories', function ($query) {
        $query->whereIn('id', Input::get('category_ids'));
})->with('latest_version')->paginate(15);

• Now the customer has requested to allow ordering the overview by certain fields, such as the title. However, since the title is not present in the projects table and the versions are loaded in a separate query after the query that is paginated, I can't seem to figure out how to do this. Joining the project_versions table into the query won't do because then I get every project x times for all the versions that exist. Sorting the collection after getting it doesn't work because this only sorts the 15 results that are being displayed on the current page.

I can also get the projects from the ProjectVersion's point of view, but there are also some fields in the projects table that need to be orderable, such as the project code.

I hope this is just something I am not seeing, or misread in the documentation, because I really don't want to step away from Laravel's pagination.