December 27th 2008 - SortPlaces v1.2.0 released: Added auto-resort when bookmarks change. This detects changes to bookmarks and automatically resorts after a short delay (in case there are lots of changes). The auto-sort is done completely silently with no pop-up window.
December 8th 2008 - SortPlaces v1.1.1 released: Minor release adds locale support for French, German, Russian, Brazilian and Polish. Also fixes some minor bugs.
November 20th 2008 - SortPlaces v1.1.0 released: Separate sort options for bookmarks menu and toolbar. Two levels of sort for menu/toolbar. Many additional "sort by" options added. Added status bar icon for quicker sorting and easier access to options.
October 16th 2008 - SortPlaces v1.0.0 released. This is the initial release of the extension based on the code in SyncPlaces.
SortPlaces is a Firefox extension that allows you to sort your bookmarks in different ways. The Bookmarks Organiser within Firefox does have some sort options, but these are not permanent and the options are not very useful.
If you wish to synchronise your bookmarks as well then you probably want the SyncPlaces extension, which also sorts bookmarks.
You can sort using the status bar icon, the option in the Bookmarks menu, or the toolbar button:
There is also an option to automatically sort your bookmarks whenever they change (see below)
You can set the sort ordering using the Options dialog, which may displayed by right mouse clicking on the status bar icon (shift-click, command-click, ctrl-click, meta-click etc. will work just as well), or by using the Options button in the Tools>Addons menu item.

You can set different sort options for the Bookmarks Menu and Toolbar separately, and for each you can set two levels of sort. On each tab use the dropdown to select what you wish to sort by.
Bookmarks, folders etc are normally sorted in increasing alphabetical or numerical order depending on the option chosen. You can use the 'Reverse order' option to change this.
Sorting of Names and Descriptions is normally done in a case sensitive way, e.g. 'a' comes before 'A'. But you can use the 'Case insensitive' option to completely ignore this when sorting (i.e. 'a' == 'A').
You can sort manually as described above, or set the 'Sort automatically' option, which will silently sort your bookmarks whenever they change (after a 5 second delay).
By default all your bookmarks are sorted. If you unselect the 'Sort all Bookmarks' checkbox then you can use the 'Select folder to sort' button to choose a single folder to sort. When the pop-up window appears, highlight the folder you wish to sort and click the OK button to accept this.
Note that bookmarks/folders/etc. are sorted within groups divided by separators. So if you have a separator in the middle of a folder, all the items above the separator will be sorted independently of all the items below it.
When sorting occurs you can decide whether to group items of the same type together and where they appear using the 'Sort order' options. Change the numbers displayed to decide how you wish to group and order the four basic bookmark items. The numbers represent where the item will appear after sorting with a lower number meaning a higher position in the results. So for example if you wish folders to always appear before queries and queries before bookmarks, with livemarks grouped together at the bottom, then set 'Folders' to '1', 'Queries' to '2', 'Bookmarks' to '3' and 'Livemarks' to '4'. If you wish two or more items to be treated equally and not grouped together, then set the order of them to be the same, e.g. set both 'Bookmarks' and 'Livemarks' to '3'.