Sort by columns break on search results

To reproduce this issue in the sandbox:

1) Click "Search ... Find Contacts" set contact type as "Organization" or "Individual"

2) In the screen displaying the results, click the column header for "state" or "country"

3) You will see the error message:

Database Error Code: Unknown column 'country' in 'order clause', 1054
Additional Details:

Array
(
[callback] => Array
(
[0] => CRM_Core_Error
[1] => handle
)

[code] => -19
[message] => DB Error: no such field
[mode] => 16
[debug_info] =>
INSERT INTO civicrm_prevnext_cache ( entity_table, entity_id1, entity_id2, cacheKey, data )
SELECT 'civicrm_contact', contact_a.id, contact_a.id, 'civicrm search 9913ed992037ec1e6204e24441ade2b0_5749', contact_a.display_name
FROM civicrm_contact contact_a LEFT JOIN civicrm_address ON ( contact_a.id = civicrm_address.contact_id AND civicrm_address.is_primary = 1 ) LEFT JOIN civicrm_country ON civicrm_address.country_id = civicrm_country.id WHERE (contact_a.is_deleted = 0) GROUP BY contact_a.id ORDER BY country asc [nativecode=1054 ** Unknown column 'country' in 'order clause']
[type] => DB_Error
[user_info] =>
INSERT INTO civicrm_prevnext_cache ( entity_table, entity_id1, entity_id2, cacheKey, data )
SELECT 'civicrm_contact', contact_a.id, contact_a.id, 'civicrm search 9913ed992037ec1e6204e24441ade2b0_5749', contact_a.display_name
FROM civicrm_contact contact_a LEFT JOIN civicrm_address ON ( contact_a.id = civicrm_address.contact_id AND civicrm_address.is_primary = 1 ) LEFT JOIN civicrm_country ON civicrm_address.country_id = civicrm_country.id WHERE (contact_a.is_deleted = 0) GROUP BY contact_a.id ORDER BY country asc [nativecode=1054 ** Unknown column 'country' in 'order clause']
[to_string] => [db_error: message="DB Error: no such field" code=-19 mode=callback callback=CRM_Core_Error::handle prefix="" info="
INSERT INTO civicrm_prevnext_cache ( entity_table, entity_id1, entity_id2, cacheKey, data )
SELECT 'civicrm_contact', contact_a.id, contact_a.id, 'civicrm search 9913ed992037ec1e6204e24441ade2b0_5749', contact_a.display_name
FROM civicrm_contact contact_a LEFT JOIN civicrm_address ON ( contact_a.id = civicrm_address.contact_id AND civicrm_address.is_primary = 1 ) LEFT JOIN civicrm_country ON civicrm_address.country_id = civicrm_country.id WHERE (contact_a.is_deleted = 0) GROUP BY contact_a.id ORDER BY country asc [nativecode=1054 ** Unknown column 'country' in 'order clause']"]
)