diff --git a/src/e-util/e-contact-store.c b/src/e-util/e-contact-store.c
index f81ffca..734aa6e 100644
--- a/src/e-util/e-contact-store.c
+++ b/src/e-util/e-contact-store.c
@@ -51,6 +51,8 @@ struct _EContactStorePrivate {
 enum {
 	START_CLIENT_VIEW,
 	STOP_CLIENT_VIEW,
+	START_UPDATE,
+	STOP_UPDATE,
 	LAST_SIGNAL
 };
 
@@ -182,6 +184,26 @@ e_contact_store_class_init (EContactStoreClass *class)
 		g_cclosure_marshal_VOID__OBJECT,
 		G_TYPE_NONE, 1,
 		E_TYPE_BOOK_CLIENT_VIEW);
+
+	signals[START_UPDATE] = g_signal_new (
+		"start-update",
+		G_OBJECT_CLASS_TYPE (object_class),
+		G_SIGNAL_RUN_LAST,
+		G_STRUCT_OFFSET (EContactStoreClass, start_update),
+		NULL, NULL,
+		g_cclosure_marshal_VOID__OBJECT,
+		G_TYPE_NONE, 1,
+		E_TYPE_BOOK_CLIENT_VIEW);
+
+	signals[STOP_UPDATE] = g_signal_new (
+		"stop-update",
+		G_OBJECT_CLASS_TYPE (object_class),
+		G_SIGNAL_RUN_LAST,
+		G_STRUCT_OFFSET (EContactStoreClass, stop_update),
+		NULL, NULL,
+		g_cclosure_marshal_VOID__OBJECT,
+		G_TYPE_NONE, 1,
+		E_TYPE_BOOK_CLIENT_VIEW);
 }
 
 static void
@@ -435,6 +457,42 @@ find_contact_by_view_and_uid (EContactStore *contact_store,
 	return -1;
 }
 
+static GHashTable *
+get_contact_hash (EContactStore *contact_store,
+                  EBookClientView *find_view)
+{
+	GArray *array;
+	ContactSource *source;
+	GPtrArray *contacts;
+	gint source_index;
+	gint ii;
+	GHashTable *hash;
+
+	source_index = find_contact_source_by_view (contact_store, find_view);
+	if (source_index < 0)
+		return NULL;
+
+	array = contact_store->priv->contact_sources;
+	source = &g_array_index (array, ContactSource, source_index);
+
+	if (find_view == source->client_view)
+		contacts = source->contacts;          /* Current view */
+	else
+		contacts = source->contacts_pending;  /* Pending view */
+
+	hash = g_hash_table_new (g_str_hash, g_str_equal);
+
+	for (ii = 0; ii < contacts->len; ii++) {
+		EContact *contact = g_ptr_array_index (contacts, ii);
+		const gchar *uid = e_contact_get_const (contact, E_CONTACT_UID);
+
+		if (uid)
+			g_hash_table_insert (hash, (gpointer) uid, GINT_TO_POINTER (ii));
+	}
+
+	return hash;
+}
+
 static gint
 find_contact_by_uid (EContactStore *contact_store,
                      const gchar *find_uid)
@@ -647,6 +705,7 @@ view_complete (EContactStore *contact_store,
 	ContactSource *source;
 	gint           offset;
 	gint           i;
+	GHashTable *hash;
 
 	if (!find_contact_source_details_by_view (contact_store, client_view, &source, &offset)) {
 		g_warning ("EContactStore got 'complete' signal from unknown EBookClientView!");
@@ -662,18 +721,17 @@ view_complete (EContactStore *contact_store,
 	g_return_if_fail (client_view == source->client_view_pending);
 
 	/* However, if it was a pending view, calculate and emit the differences between that
-	 * and the current view, and move the pending view up to current.
-	 *
-	 * This is O(m * n), and can be sped up with a temporary hash table if needed. */
+	 * and the current view, and move the pending view up to current. */
 
+	g_signal_emit (contact_store, signals[START_UPDATE], 0, client_view);
+ 
 	/* Deletions */
+	hash = get_contact_hash (contact_store, source->client_view_pending);
 	for (i = 0; i < source->contacts->len; i++) {
 		EContact    *old_contact = g_ptr_array_index (source->contacts, i);
 		const gchar *old_uid = e_contact_get_const (old_contact, E_CONTACT_UID);
-		gint         result;
 
-		result = find_contact_by_view_and_uid (contact_store, source->client_view_pending, old_uid);
-		if (result < 0) {
+		if (!g_hash_table_contains (hash, old_uid)) {
 			/* Contact is not in new view; removed */
 			g_object_unref (old_contact);
 			g_ptr_array_remove_index (source->contacts, i);
@@ -681,15 +739,15 @@ view_complete (EContactStore *contact_store,
 			i--;  /* Stay in place */
 		}
 	}
+	g_hash_table_unref (hash);
 
 	/* Insertions */
+	hash = get_contact_hash (contact_store, source->client_view);
 	for (i = 0; i < source->contacts_pending->len; i++) {
 		EContact    *new_contact = g_ptr_array_index (source->contacts_pending, i);
 		const gchar *new_uid = e_contact_get_const (new_contact, E_CONTACT_UID);
-		gint         result;
 
-		result = find_contact_by_view_and_uid (contact_store, source->client_view, new_uid);
-		if (result < 0) {
+		if (!g_hash_table_contains (hash, new_uid)) {
 			/* Contact is not in old view; inserted */
 			g_ptr_array_add (source->contacts, new_contact);
 			row_inserted (contact_store, offset + source->contacts->len - 1);
@@ -698,6 +756,9 @@ view_complete (EContactStore *contact_store,
 			g_object_unref (new_contact);
 		}
 	}
+	g_hash_table_unref (hash);
+
+	g_signal_emit (contact_store, signals[STOP_UPDATE], 0, client_view);
 
 	/* Move pending view up to current */
 	stop_view (contact_store, source->client_view);
diff --git a/src/e-util/e-contact-store.h b/src/e-util/e-contact-store.h
index f6a5ead..4d25f7a 100644
--- a/src/e-util/e-contact-store.h
+++ b/src/e-util/e-contact-store.h
@@ -67,6 +67,10 @@ struct _EContactStoreClass {
 						 EBookClientView *client_view);
 	void		(*stop_client_view)	(EContactStore *contact_store,
 						 EBookClientView *client_view);
+	void		(*start_update)		(EContactStore *contact_store,
+						 EBookClientView *client_view);
+	void		(*stop_update)		(EContactStore *contact_store,
+						 EBookClientView *client_view);
 };
 
 GType		e_contact_store_get_type	(void) G_GNUC_CONST;
diff --git a/src/e-util/e-name-selector-dialog.c b/src/e-util/e-name-selector-dialog.c
index f2db4d7..214fa6e 100644
--- a/src/e-util/e-name-selector-dialog.c
+++ b/src/e-util/e-name-selector-dialog.c
@@ -1129,11 +1129,53 @@ view_progress (EBookClientView *view,
 }
 
 static void
+enable_sort (ENameSelectorDialog *dialog)
+{
+	ETreeModelGenerator *contact_filter;
+
+	/* Get contact store and its filter wrapper */
+
+	contact_filter = e_name_selector_model_peek_contact_filter (
+		dialog->priv->name_selector_model);
+
+	/* Create sorting model on top of filter, assign it to view */
+
+	if (!dialog->priv->contact_sort) {
+		dialog->priv->contact_sort = GTK_TREE_MODEL_SORT (
+			gtk_tree_model_sort_new_with_model (GTK_TREE_MODEL (contact_filter)));
+
+		/* sort on full name as we display full name in name selector dialog */
+		gtk_tree_sortable_set_sort_column_id (
+			GTK_TREE_SORTABLE (dialog->priv->contact_sort),
+			E_CONTACT_FULL_NAME, GTK_SORT_ASCENDING);
+	}
+
+	gtk_tree_view_set_model (
+		dialog->priv->contact_view,
+		GTK_TREE_MODEL (dialog->priv->contact_sort));
+}
+
+static void
+disable_sort (ENameSelectorDialog *dialog)
+{
+	if (dialog->priv->contact_sort) {
+		g_object_unref (dialog->priv->contact_sort);
+		dialog->priv->contact_sort = NULL;
+	}
+
+	gtk_tree_view_set_model (
+		dialog->priv->contact_view,
+		NULL);
+}
+
+static void
 view_complete (EBookClientView *view,
                const GError *error,
                ENameSelectorDialog *dialog)
 {
 	view_progress (view, -1, NULL, dialog);
+
+	enable_sort (dialog);
 }
 
 static void
@@ -1160,6 +1202,22 @@ stop_client_view_cb (EContactStore *store,
 }
 
 static void
+start_update_cb (EContactStore *store,
+                 EBookClientView *client_view,
+                 ENameSelectorDialog *name_selector_dialog)
+{
+	disable_sort (name_selector_dialog);
+}
+
+static void
+stop_update_cb (EContactStore *store,
+                EBookClientView *client_view,
+                ENameSelectorDialog *name_selector_dialog)
+{
+	enable_sort (name_selector_dialog);
+}
+
+static void
 name_selector_dialog_get_client_cb (GObject *source_object,
                                     GAsyncResult *result,
                                     gpointer user_data)
@@ -1589,7 +1647,6 @@ transfer_button_clicked (ENameSelectorDialog *name_selector_dialog,
 static void
 setup_name_selector_model (ENameSelectorDialog *name_selector_dialog)
 {
-	ETreeModelGenerator *contact_filter;
 	EContactStore       *contact_store;
 	GList               *new_sections;
 	GList               *l;
@@ -1625,29 +1682,12 @@ setup_name_selector_model (ENameSelectorDialog *name_selector_dialog)
 		name_selector_dialog->priv->name_selector_model, "section-removed",
 		G_CALLBACK (model_section_removed), name_selector_dialog);
 
-	/* Get contact store and its filter wrapper */
-
-	contact_filter = e_name_selector_model_peek_contact_filter (
-		name_selector_dialog->priv->name_selector_model);
-
-	/* Create sorting model on top of filter, assign it to view */
-
-	name_selector_dialog->priv->contact_sort = GTK_TREE_MODEL_SORT (
-		gtk_tree_model_sort_new_with_model (GTK_TREE_MODEL (contact_filter)));
-
-	/* sort on full name as we display full name in name selector dialog */
-	gtk_tree_sortable_set_sort_column_id (
-		GTK_TREE_SORTABLE (name_selector_dialog->priv->contact_sort),
-		E_CONTACT_FULL_NAME, GTK_SORT_ASCENDING);
-
-	gtk_tree_view_set_model (
-		name_selector_dialog->priv->contact_view,
-		GTK_TREE_MODEL (name_selector_dialog->priv->contact_sort));
-
 	contact_store = e_name_selector_model_peek_contact_store (name_selector_dialog->priv->name_selector_model);
 	if (contact_store) {
 		g_signal_connect (contact_store, "start-client-view", G_CALLBACK (start_client_view_cb), name_selector_dialog);
 		g_signal_connect (contact_store, "stop-client-view", G_CALLBACK (stop_client_view_cb), name_selector_dialog);
+		g_signal_connect (contact_store, "start-update", G_CALLBACK (start_update_cb), name_selector_dialog);
+		g_signal_connect (contact_store, "stop-update", G_CALLBACK (stop_update_cb), name_selector_dialog);
 	}
 
 	/* Make sure UI is consistent */
