diff --git a/bundles/org.eclipse.osgi/resolver/src/org/eclipse/osgi/internal/module/MappedList.java b/bundles/org.eclipse.osgi/resolver/src/org/eclipse/osgi/internal/module/MappedList.java
index 4fc99a4..46e4afd 100644
--- a/bundles/org.eclipse.osgi/resolver/src/org/eclipse/osgi/internal/module/MappedList.java
+++ b/bundles/org.eclipse.osgi/resolver/src/org/eclipse/osgi/internal/module/MappedList.java
@@ -1,5 +1,5 @@
 /*******************************************************************************
- * Copyright (c) 2005 IBM Corporation and others.
+ * Copyright (c) 2005, 2008 IBM Corporation and others.
  * All rights reserved. This program and the accompanying materials
  * are made available under the terms of the Eclipse Public License v1.0
  * which accompanies this distribution, and is available at
@@ -28,18 +28,20 @@
 			existing[0] = value;
 			internal.put(key, existing);
 		} else {
-			// append the new value to the end.
+			// insert the new value
+			int index = insertionIndex(existing, value);
 			Object[] newValues = new Object[existing.length + 1];
-			System.arraycopy(existing, 0, newValues, 0, existing.length);
-			newValues[existing.length] = value;
-			sort(newValues); // sort the new values array
-			internal.put(key, newValues); // overwrite the old values in tha map
+			System.arraycopy(existing, 0, newValues, 0, index);
+			newValues[index] = value;
+			System.arraycopy(existing, index, newValues, index + 1, existing.length - index);
+			internal.put(key, newValues); // overwrite the old values in the map
 		}
 	}
 
-	protected void sort(Object[] values) {
-		// a MappedList is not sorted by default
-		// extending classes may override this method to sort lists
+	protected int insertionIndex(Object[] existing, Object value) {
+		// a MappedList is by default not sorted so just insert at the end
+		// extending classes may override this method to provide an index that retains sorted order
+		return existing.length;
 	}
 
 	// removes all values with the specified key
diff --git a/bundles/org.eclipse.osgi/resolver/src/org/eclipse/osgi/internal/module/VersionHashMap.java b/bundles/org.eclipse.osgi/resolver/src/org/eclipse/osgi/internal/module/VersionHashMap.java
index 142461e..ee69379 100644
--- a/bundles/org.eclipse.osgi/resolver/src/org/eclipse/osgi/internal/module/VersionHashMap.java
+++ b/bundles/org.eclipse.osgi/resolver/src/org/eclipse/osgi/internal/module/VersionHashMap.java
@@ -20,9 +20,16 @@
 		this.resolver = resolver;
 	}
 
-	// sorts using the Comparator#compare method to sort
-	protected void sort(Object[] values) {
-		Arrays.sort(values, this);
+	// assumes existing array is sorted
+	// finds the index where to insert the new value
+	protected int insertionIndex(Object[] existing, Object value) {
+		int index = existing.length;
+		if (compare(existing[existing.length - 1], value) > 0) {
+			index = Arrays.binarySearch(existing, value, this);
+			if (index < 0)
+				index = -index - 1;
+		}
+		return index;
 	}
 
 	public void put(VersionSupplier[] versionSuppliers) {
@@ -72,7 +79,7 @@
 			Object[] existing = (Object[]) it.next();
 			if (existing.length <= 1)
 				continue;
-			sort(existing);
+			Arrays.sort(existing, this);
 		}
 	}