I finally decided to use the Tag property on Navigation Bar locations to hold the value that I wish to sort by.

I created a Comparer class as follows:

    public class LocationTagComparer : System.Collections.Generic.IComparer<UltraNavigationBarLocation>
    {
        int IComparer<UltraNavigationBarLocation>.Compare(UltraNavigationBarLocation first, UltraNavigationBarLocation second)
        {
            if (first == null & second == null) { return 0; }
            else if (first == null) { return -1; }
            else if (second == null) { return 1; }
            else
            {
                return first.Settings.Tag.ToString().CompareTo(second.Settings.Tag.ToString());
            }
        }
    }

After building the location list, use a comparer object to do the sorting:
            this.ultraNavigationBar1.RootLocation.Locations.VisibleMembers.Sort(new LocationTagComparer());

Add code to the Location Expanding event.  

    private void ultraNavigationBar1_LocationExpanding(object sender, Infragistics.Win.Misc.UltraWinNavigationBar.LocationExpandingEventArgs e)
    {
        if (e.Location.Level == -1)
        {
            e.Location.Locations.VisibleMembers.Sort(new LocationTagComparer());
        }
    }

Hope this helps.

The code posted here is the recommended way to sort the list that is presented to the end user, except for one thing - the first line of code in the LocationExpanding handler, "if (e.Location.Level == -1)" should be changed to (something like) "if ( e.Location == this.ultraNavigationBar1.RootLocation )", because the Level property is not supposed to return -1 for the root location, and that fact that it does is a bug that will be addressed in a future release.

You should be able to use this approach to "sort" the visible list by the location's Index property, which reflects its ordinal position within the collection, not the visible position, if you want the locations to appear in the same order that you added them.

I was not able to observe any problems with the "...highlighting of the item get slower and slower and slower" using the Infragistics File Explorer sample, so you might want to log a bug report for that and include a sample that demonstrates the behavior so that it can be addressed.

Thanks for the clarification on the Level == -1 issue.  I'm sure that would have caused me a lot of head-scratching when that issue is addressed.

Thanks, that Comparer did the trick.

I can't reproduce the slowness again, oh well.

Cheers.