First, you will need to create an XSLT file and download an XSLT processor. Open TextEdit, and cut and paste this XSLT code and save. I named mine SortSafariBookmarks.xslt.
Next you will have to download Marc Liyanage's TestXSLT and install it -- or you can use a different XSLT processor if you wish.
The Safari Bookmarks.plist file is an XML file (in 10.3) or can be converted into an XML file (in 10.4). If you're running 10.4, use this hint, Convert new plist files between XML and binary, to convert the Safari bookmarks file into XML. Open Terminal and type this command (of course, replace username with your short username):
plutil -convert xml1 /Users/username/Library/Safari/Bookmarks.plist
Once you have the Bookmarks.plist file converted, you can either use TestXSLT to process the Bookmarks.plist file with the XSLT file, or you can use this AppleScript to process it. I am not an AppleScript expert, but the demo AppleScript that was provided with TestXSLT was very helpful.
Paste the script into Script Editor and save it. Then run the AppleScript. Your Bookmarks.plist file is now sorted. You just have to convert it back to a binary plist file if you're running 10.4. To do that, you just need to run this command in the Terminal (again, change username to your short user name):
plutil -convert binary1 /Users/username/Library/Safari/Bookmarks.plist
[robg adds: I haven't tested this one...]

