Index: trunk/src/org/openstreetmap/josm/data/APIDataSet.java
===================================================================
--- trunk/src/org/openstreetmap/josm/data/APIDataSet.java	(revision 13017)
+++ trunk/src/org/openstreetmap/josm/data/APIDataSet.java	(revision 13018)
@@ -213,10 +213,10 @@
 
         RelationUploadDependencyGraph graph = new RelationUploadDependencyGraph(relationsToAdd, true);
-        newToAdd.addAll(graph.computeUploadOrder());
+        newToAdd.addAll(graph.computeUploadOrder(false));
         toAdd = newToAdd;
 
         List<OsmPrimitive> newToDelete = new LinkedList<>();
         graph = new RelationUploadDependencyGraph(Utils.filteredCollection(toDelete, Relation.class), false);
-        newToDelete.addAll(graph.computeUploadOrder());
+        newToDelete.addAll(graph.computeUploadOrder(true));
         newToDelete.addAll(Utils.filteredCollection(toDelete, Way.class));
         newToDelete.addAll(Utils.filteredCollection(toDelete, Node.class));
@@ -305,5 +305,5 @@
         }
 
-        public List<Relation> computeUploadOrder() throws CyclicUploadDependencyException {
+        public List<Relation> computeUploadOrder(boolean reverse) throws CyclicUploadDependencyException {
             visited = new HashSet<>();
             uploadOrder = new LinkedList<>();
@@ -313,5 +313,9 @@
             }
             List<Relation> ret = new ArrayList<>(relations);
-            ret.sort(Comparator.comparingInt(uploadOrder::indexOf));
+            Comparator<? super Relation> cmpr = Comparator.comparingInt(uploadOrder::indexOf);
+            if (reverse) {
+                cmpr = cmpr.reversed();
+            }
+            ret.sort(cmpr);
             return ret;
         }