Update: Compatible version available Rated 5 out of 5 stars

This add-on is still needed since adjusting the about:config formfill preferences cannot provide a really consistent sort order: Most recent: first or last, alphabetically. For example I would need most recent first, meaning sorted consistent by time.

A Firefox compatible version of Searchbar Autocomplete Order is available here (scroll down to the very bottom): http://netticat.ath.cx/MyAddons/MyAddons.htm
I am also developer on AMO (https://addons.mozilla.org/en-US/firefox/user/516763/)

Alternatively the current sort algorithm is configurable with the preferences browser.formfill. and works as follows (from https://wiki.mozilla.org/Firefox/Namoroka/Improved_form_history):

Frecency Calculation:
a = timesUsed
b = lastUsed - firstUsed
c = lastUsed multiple
d = agedBonus (for entries that have survived expiration)
frecency = a/b * c * d

* browser.formfill.
o agedWeight - multiply the score by this value for entries that have
survived expiration
o boundaryWeight - how much weight (in %) to add to word boundary matches
o bucketSize - range of relevancy values to group together and sort
o maxTimeGroupings - maximum number of timeGroupingSize units to give a bonus
o prefixWeight - multiply the score by this value for exact prefix matches
o timeGroupingSize - number of seconds in a time container

This review is for a previous version of the add-on (2.2).