--- a/toolkit/components/places/Bookmarks.jsm
+++ b/toolkit/components/places/Bookmarks.jsm
@@ -1156,25 +1156,38 @@ function removeBookmark(item, options) {
 function reorderChildren(parent, orderedChildrenGuids) {
   return PlacesUtils.withConnectionWrapper("Bookmarks.jsm: updateBookmark",
     db => db.executeTransaction(function* () {
       // Select all of the direct children for the given parent.
       let children = yield fetchBookmarksByParent({ parentGuid: parent.guid });
       if (!children.length)
         return undefined;
 
+      // Build a map of GUIDs to indices for fast lookups in the comparator
+      // function.
+      let guidIndices = new Map();
+      for (let i = 0; i < orderedChildrenGuids.length; ++i) {
+        let guid = orderedChildrenGuids[i];
+        guidIndices.set(guid, i);
+      }
+
       // Reorder the children array according to the specified order, provided
       // GUIDs come first, others are appended in somehow random order.
       children.sort((a, b) => {
-        let i = orderedChildrenGuids.indexOf(a.guid);
-        let j = orderedChildrenGuids.indexOf(b.guid);
         // This works provided fetchBookmarksByParent returns sorted children.
-        if (i == -1 && j == -1)
+        if (!guidIndices.has(a.guid) && !guidIndices.has(b.guid)) {
           return 0;
-        return (i != -1 && j != -1 && i < j) || (i != -1 && j == -1) ? -1 : 1;
+        }
+        if (!guidIndices.has(a.guid)) {
+          return 1;
+        }
+        if (!guidIndices.has(b.guid)) {
+          return -1;
+        }
+        return guidIndices.get(a.guid) < guidIndices.get(b.guid) ? -1 : 1;
        });
 
       // Update the bookmarks position now.  If any unknown guid have been
       // inserted meanwhile, its position will be set to -position, and we'll
       // handle it later.
       // To do the update in a single step, we build a VALUES (guid, position)
       // table.  We then use count() in the sorting table to avoid skipping values
       // when no more existing GUIDs have been provided.

--- a/toolkit/components/places/PlacesSyncUtils.jsm
+++ b/toolkit/components/places/PlacesSyncUtils.jsm
@@ -104,67 +104,36 @@ const BookmarkSyncUtils = PlacesSyncUtil
     let db = yield PlacesUtils.promiseDBConnection();
     let children = yield fetchAllChildren(db, parentGuid);
     return children.map(child =>
       BookmarkSyncUtils.guidToSyncId(child.guid)
     );
   }),
 
   /**
-   * Reorders a folder's children, based on their order in the array of GUIDs.
-   * This method is similar to `Bookmarks.reorder`, but leaves missing entries
-   * in place instead of moving them to the end of the folder.
+   * Reorders a folder's children, based on their order in the array of sync
+   * IDs.
    *
    * Sync uses this method to reorder all synced children after applying all
    * incoming records.
    *
    */
   order: Task.async(function* (parentSyncId, childSyncIds) {
     PlacesUtils.SYNC_BOOKMARK_VALIDATORS.syncId(parentSyncId);
     if (!childSyncIds.length) {
       return;
     }
-    for (let syncId of childSyncIds) {
-      PlacesUtils.SYNC_BOOKMARK_VALIDATORS.syncId(syncId);
-    }
     let parentGuid = BookmarkSyncUtils.syncIdToGuid(parentSyncId);
-
     if (parentGuid == PlacesUtils.bookmarks.rootGuid) {
       // Reordering roots doesn't make sense, but Sync will do this on the
       // first sync.
       return;
     }
-    yield PlacesUtils.withConnectionWrapper("BookmarkSyncUtils: order",
-      Task.async(function* (db) {
-        let children = yield fetchAllChildren(db, parentGuid);
-        if (!children.length) {
-          return;
-        }
-
-        // Reorder the list, ignoring missing children.
-        let delta = 0;
-        for (let i = 0; i < childSyncIds.length; ++i) {
-          let guid = BookmarkSyncUtils.syncIdToGuid(childSyncIds[i]);
-          let child = findChildByGuid(children, guid);
-          if (!child) {
-            delta++;
-            BookmarkSyncLog.trace(`order: Ignoring missing child ${
-              childSyncIds[i]}`);
-            continue;
-          }
-          let newIndex = i - delta;
-          updateChildIndex(children, child, newIndex);
-        }
-        children.sort((a, b) => a.index - b.index);
-
-        // Update positions.
-        let orderedChildrenGuids = children.map(({ guid }) => guid);
-        yield PlacesUtils.bookmarks.reorder(parentGuid, orderedChildrenGuids);
-      })
-    );
+    let orderedChildrenGuids = childSyncIds.map(BookmarkSyncUtils.syncIdToGuid);
+    return PlacesUtils.bookmarks.reorder(parentGuid, orderedChildrenGuids);
   }),
 
   /**
    * Removes an item from the database.
    */
   remove: Task.async(function* (syncId) {
     let guid = BookmarkSyncUtils.syncIdToGuid(syncId);
     if (guid in ROOT_GUID_TO_SYNC_ID) {
@@ -368,41 +337,16 @@ var fetchAllChildren = Task.async(functi
     id: row.getResultByName("id"),
     parentId: row.getResultByName("parent"),
     index: row.getResultByName("position"),
     type: row.getResultByName("type"),
     guid: row.getResultByName("guid"),
   }));
 });
 
-function findChildByGuid(children, guid) {
-  return children.find(child => child.guid == guid);
-}
-
-function findChildByIndex(children, index) {
-  return children.find(child => child.index == index);
-}
-
-// Sets a child record's index and updates its sibling's indices.
-function updateChildIndex(children, child, newIndex) {
-  let siblings = [];
-  let lowIndex = Math.min(child.index, newIndex);
-  let highIndex = Math.max(child.index, newIndex);
-  for (; lowIndex < highIndex; ++lowIndex) {
-    let sibling = findChildByIndex(children, lowIndex);
-    siblings.push(sibling);
-  }
-
-  let sign = newIndex < child.index ? +1 : -1;
-  for (let sibling of siblings) {
-    sibling.index += sign;
-  }
-  child.index = newIndex;
-}
-
 // A helper for whenever we want to know if a GUID doesn't exist in the places
 // database. Primarily used to detect orphans on incoming records.
 var GUIDMissing = Task.async(function* (guid) {
   try {
     yield PlacesUtils.promiseItemId(guid);
     return false;
   } catch (ex) {
     if (ex.message == "no item found for the given GUID") {