Index: /trunk/src/org/openstreetmap/josm/gui/DefaultNameFormatter.java
===================================================================
--- /trunk/src/org/openstreetmap/josm/gui/DefaultNameFormatter.java	(revision 5082)
+++ /trunk/src/org/openstreetmap/josm/gui/DefaultNameFormatter.java	(revision 5083)
@@ -34,4 +34,5 @@
 import org.openstreetmap.josm.data.osm.history.HistoryWay;
 import org.openstreetmap.josm.gui.tagging.TaggingPreset;
+import org.openstreetmap.josm.tools.AlphanumComparator;
 import org.openstreetmap.josm.tools.I18n;
 import org.openstreetmap.josm.tools.TaggingPresetNameTemplateList;
@@ -349,4 +350,5 @@
 
     private final Comparator<Relation> relationComparator = new Comparator<Relation>() {
+        private final AlphanumComparator ALPHANUM_COMPARATOR = new AlphanumComparator();
         @Override
         public int compare(Relation r1, Relation r2) {
@@ -370,5 +372,5 @@
                 String type2 = getRelationTypeName(r2);
 
-                int comp = type1.compareTo(type2);
+                int comp = ALPHANUM_COMPARATOR.compare(type1, type2);
                 if (comp != 0)
                     return comp;
@@ -377,34 +379,6 @@
                 String name2 = getRelationName(r2);
 
-                if (name1 == null && name2 == null)
-                    return (r1.getUniqueId() > r2.getUniqueId())?1:-1;
-                else if (name1 == null)
-                    return -1;
-                else if (name2 == null)
-                    return 1;
-                else if (!name1.isEmpty() && !name2.isEmpty() && Character.isDigit(name1.charAt(0)) && Character.isDigit(name2.charAt(0))) {
-                    //Compare numerically
-                    String ln1 = getLeadingNumber(name1);
-                    String ln2 = getLeadingNumber(name2);
-
-                    comp = Long.valueOf(ln1).compareTo(Long.valueOf(ln2));
-                    if (comp != 0)
-                        return comp;
-
-                    // put 1 before 0001
-                    comp = ln1.compareTo(ln2);
-                    if (comp != 0)
-                        return comp;
-
-                    comp = name1.substring(ln1.length()).compareTo(name2.substring(ln2.length()));
-                    if (comp != 0)
-                        return comp;
-                } else {
-                    comp = name1.compareToIgnoreCase(name2);
-                    if (comp != 0)
-                        return comp;
-                }
-            }
-
+                return ALPHANUM_COMPARATOR.compare(name1, name2);
+            }
 
             if (r1.getMembersCount() != r2.getMembersCount())
Index: /trunk/src/org/openstreetmap/josm/tools/AlphanumComparator.java
===================================================================
--- /trunk/src/org/openstreetmap/josm/tools/AlphanumComparator.java	(revision 5083)
+++ /trunk/src/org/openstreetmap/josm/tools/AlphanumComparator.java	(revision 5083)
@@ -0,0 +1,111 @@
+package org.openstreetmap.josm.tools;
+
+/*
+ * The Alphanum Algorithm is an improved sorting algorithm for strings
+ * containing numbers. Instead of sorting numbers in ASCII order like a standard
+ * sort, this algorithm sorts numbers in numeric order.
+ *
+ * The Alphanum Algorithm is discussed at http://www.DaveKoelle.com
+ *
+ *
+ * This library is free software; you can redistribute it and/or modify it under
+ * the terms of the GNU Lesser General Public License as published by the Free
+ * Software Foundation; either version 2.1 of the License, or any later version.
+ *
+ * This library is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+ * FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more
+ * details.
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with this library; if not, write to the Free Software Foundation, Inc.,
+ * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ *
+ */
+import java.util.Comparator;
+
+/**
+ * The Alphanum Algorithm is an improved sorting algorithm for strings
+ * containing numbers: Instead of sorting numbers in ASCII order like a standard
+ * sort, this algorithm sorts numbers in numeric order.
+ *
+ * The Alphanum Algorithm is discussed at http://www.DaveKoelle.com
+ * 
+ * This is an updated version with enhancements made by Daniel Migowski, Andre
+ * Bogus, and David Koelle.
+ *
+ */
+public class AlphanumComparator implements Comparator<String> {
+
+    /**
+     * Length of string is passed in for improved efficiency (only need to
+     * calculate it once) *
+     */
+    private String getChunk(String s, int slength, int marker) {
+        StringBuilder chunk = new StringBuilder();
+        char c = s.charAt(marker);
+        chunk.append(c);
+        marker++;
+        if (Character.isDigit(c)) {
+            while (marker < slength) {
+                c = s.charAt(marker);
+                if (!Character.isDigit(c)) {
+                    break;
+                }
+                chunk.append(c);
+                marker++;
+            }
+        } else {
+            while (marker < slength) {
+                c = s.charAt(marker);
+                if (Character.isDigit(c)) {
+                    break;
+                }
+                chunk.append(c);
+                marker++;
+            }
+        }
+        return chunk.toString();
+    }
+
+    @Override
+    public int compare(String s1, String s2) {
+        int thisMarker = 0;
+        int thatMarker = 0;
+        int s1Length = s1.length();
+        int s2Length = s2.length();
+
+        while (thisMarker < s1Length && thatMarker < s2Length) {
+            String thisChunk = getChunk(s1, s1Length, thisMarker);
+            thisMarker += thisChunk.length();
+
+            String thatChunk = getChunk(s2, s2Length, thatMarker);
+            thatMarker += thatChunk.length();
+
+            // If both chunks contain numeric characters, sort them numerically
+            int result;
+            if (Character.isDigit(thisChunk.charAt(0)) && Character.isDigit(thatChunk.charAt(0))) {
+                // Simple chunk comparison by length.
+                int thisChunkLength = thisChunk.length();
+                result = thisChunkLength - thatChunk.length();
+                // If equal, the first different number counts
+                if (result == 0) {
+                    for (int i = 0; i < thisChunkLength; i++) {
+                        result = thisChunk.charAt(i) - thatChunk.charAt(i);
+                        if (result != 0) {
+                            return result;
+                        }
+                    }
+                }
+            } else {
+                result = thisChunk.compareTo(thatChunk);
+            }
+
+            if (result != 0) {
+                return result;
+            }
+        }
+
+        return s1Length - s2Length;
+    }
+}