Since it doesn't do it by default, and there's no built-in mechanism to do so, this dude wrote a script called Sortasaurus that will close Safari if it's running, sort your bookmarks bar alphabetically, and reopen Safari.
James Howard's Home Page
But then my Full Screen bookmark wouldn't be the first on my bar.
Go into bookmarks and create a new bookmark with this as the address. Make sure it is in the Bookmarks bar folder so that you can access it quickly.