diff --git a/src/qcbor_encode.c b/src/qcbor_encode.c
index 76f2923..6b591d5 100644
--- a/src/qcbor_encode.c
+++ b/src/qcbor_encode.c
@@ -1178,7 +1178,7 @@
 
 
 /**
- * @brief  Decoded next item to get its length.
+ * @brief  Decoded next item to get its lengths.
  *
  * Decode the next item in map no matter what type it is. It works
  * recursively when an item is a map or array It returns offset just
@@ -1190,16 +1190,25 @@
  * stuff that came in from outside. We still want a check for safety
  * in case of bugs here, but it is OK to report end of input on error.
  */
-static uint32_t
+struct ItemLens {
+   uint32_t  uLabelLen;
+   uint32_t  uItemLen;
+};
+
+static struct ItemLens
 QCBOREncode_Private_DecodeNextInMap(QCBOREncodeContext *pMe, uint32_t uStart)
 {
-   UsefulInputBuf InBuf;
-   UsefulBufC     EncodedMapBytes;
-   QCBORError     uCBORError;
+   UsefulInputBuf  InBuf;
+   UsefulBufC      EncodedMapBytes;
+   QCBORError      uCBORError;
+   struct ItemLens Result;
+
+   Result.uLabelLen = 0;
+   Result.uItemLen  = 0;
 
    EncodedMapBytes = UsefulOutBuf_OutUBufOffset(&(pMe->OutBuf), uStart);
    if(UsefulBuf_IsNULLC(EncodedMapBytes)) {
-      return 0;
+      return Result;
    }
 
    UsefulInputBuf_Init(&InBuf, EncodedMapBytes);
@@ -1207,15 +1216,22 @@
    /* This is always used on maps, so consume two, the label and the value */
    uCBORError = QCBOR_Private_ConsumeNext(&InBuf);
    if(uCBORError) {
-      return 0;
-   }
-   uCBORError = QCBOR_Private_ConsumeNext(&InBuf);
-   if(uCBORError) {
-      return 0;
+      return Result;
    }
 
    /* Cast is safe because this is QCBOR which limits sizes to UINT32_MAX */
-   return (uint32_t)UsefulInputBuf_Tell(&InBuf);
+   Result.uLabelLen = (uint32_t)UsefulInputBuf_Tell(&InBuf);
+
+   uCBORError = QCBOR_Private_ConsumeNext(&InBuf);
+   if(uCBORError) {
+      Result.uLabelLen = 0;
+      return Result;
+   }
+
+   Result.uItemLen = (uint32_t)UsefulInputBuf_Tell(&InBuf);
+
+   /* Cast is safe because this is QCBOR which limits sizes to UINT32_MAX */
+   return Result;
 }
 
 
@@ -1233,12 +1249,13 @@
 static void
 QCBOREncode_Private_SortMap(QCBOREncodeContext *pMe, uint32_t uStart)
 {
-   bool     bSwapped;
-   int      nComparison;
-   uint32_t uLen2;
-   uint32_t uLen1;
-   uint32_t uStart1;
-   uint32_t uStart2;
+   bool            bSwapped;
+   int             nComparison;
+   uint32_t        uStart1;
+   uint32_t        uStart2;
+   struct ItemLens Lens1;
+   struct ItemLens Lens2;
+
 
    if(pMe->uError != QCBOR_SUCCESS) {
       return;
@@ -1259,35 +1276,37 @@
     * swapped.
     */
    do {
-      uLen1 = QCBOREncode_Private_DecodeNextInMap(pMe, uStart);
-      if(uLen1 == 0) {
+      Lens1 = QCBOREncode_Private_DecodeNextInMap(pMe, uStart);
+      if(Lens1.uLabelLen == 0) {
          /* It's an empty map. Nothing to do. */
          break;
       }
       uStart1 = uStart;
-      uStart2 = uStart1 + uLen1;
+      uStart2 = uStart1 + Lens1.uItemLen;
       bSwapped = false;
 
       while(1) {
-         uLen2 = QCBOREncode_Private_DecodeNextInMap(pMe, uStart2);
-         if(uLen2 == 0) {
+         Lens2 = QCBOREncode_Private_DecodeNextInMap(pMe, uStart2);
+         if(Lens2.uLabelLen == 0) {
             break;
          }
 
          nComparison = UsefulOutBuf_Compare(&(pMe->OutBuf),
-                                            uStart1, (uStart2 - uStart1),
-                                            uStart2, uLen2);
+                                            uStart1, Lens1.uLabelLen,
+                                            uStart2, Lens2.uLabelLen);
          if(nComparison < 0) {
-            UsefulOutBuf_Swap(&(pMe->OutBuf), uStart1, uStart2, uStart2 + uLen2);
-            uStart1 = uStart1 + uLen2;
+            UsefulOutBuf_Swap(&(pMe->OutBuf), uStart1, uStart2, uStart2 + Lens2.uItemLen);
+            uStart1 = uStart1 + Lens2.uItemLen; /* item 2 now in position of item 1 */
+            /* Lens1 is still valid as Lens1 for the next loop */
             bSwapped = true;
          } else if (nComparison > 0) {
             uStart1 = uStart2;
+            Lens1   = Lens2;
          } else /* nComparison == 0 */ {
             pMe->uError = QCBOR_ERR_DUPLICATE_LABEL;
             return;
          }
-         uStart2 = uStart2 + uLen2;
+         uStart2 = uStart2 + Lens2.uItemLen;
       }
    } while(bSwapped);
 }
diff --git a/test/qcbor_encode_tests.c b/test/qcbor_encode_tests.c
index 8c609bc..07decec 100644
--- a/test/qcbor_encode_tests.c
+++ b/test/qcbor_encode_tests.c
@@ -3146,6 +3146,43 @@
    if(uErr) {
       return 31;
    }
+
+
+   /*
+
+10 - 64               # text(4)
+       6E756C6C      # "null"
+    F6               # primitive(22)
+16 -  65               # text(5)
+       6172726179    # "array"
+    82               # array(2)
+       62            # text(2)
+          6869       # "hi"
+       65            # text(5)
+          7468657265 # "there"
+32 - 66               # text(6)
+       656D70747931  # "empty1"
+    A0               # map(0)
+40 - 66               # text(6)
+       656D70747932  # "empty2"
+    A0               # map(0)
+
+    */
+   /* {
+        88: 1(888888),
+        428: {
+          "null": null,
+          "array": [
+            "hi",
+            "there"
+          ],
+          "empty1": {},
+          "empty2": {}
+        },
+        "boo": true,
+        "three": 3
+      }
+    */
    static const uint8_t spNested[] = {
       0xA4, 0x18, 0x58, 0xC1, 0x1A, 0x00, 0x0D, 0x90,
       0x38, 0x19, 0x01, 0xAC, 0xA4, 0x64, 0x6E, 0x75,
@@ -3162,6 +3199,69 @@
       return 32;
    }
 
+
+/* Same data items, but added in a different order */
+   QCBOREncode_Init(&EC, TestBuf);
+   QCBOREncode_OpenMap(&EC);
+     QCBOREncode_AddInt64ToMap(&EC, "three", 3);
+     QCBOREncode_OpenMapInMapN(&EC, 428);
+       QCBOREncode_OpenMapInMap(&EC, "empty1");
+         QCBOREncode_CloseAndSortMap(&EC);
+       QCBOREncode_OpenArrayInMap(&EC, "array");
+         QCBOREncode_AddSZString(&EC, "hi");
+         QCBOREncode_AddSZString(&EC, "there");
+         QCBOREncode_CloseArray(&EC);
+       QCBOREncode_OpenMapInMap(&EC, "empty2");
+         QCBOREncode_CloseAndSortMap(&EC);
+       QCBOREncode_AddNULLToMap(&EC, "null");
+       QCBOREncode_CloseAndSortMap(&EC);
+     QCBOREncode_AddDateEpochToMapN(&EC, 88, 888888);
+     QCBOREncode_AddBoolToMap(&EC, "boo", true);
+     QCBOREncode_CloseAndSortMap(&EC);
+   uErr = QCBOREncode_Finish(&EC, &EncodedAndSorted);
+   if(uErr) {
+      return 31;
+   }
+
+   if(UsefulBuf_CompareWithDiagnostic(EncodedAndSorted,
+                                      UsefulBuf_FROM_BYTE_ARRAY_LITERAL(spNested),
+                                      &CompareDiagnostics)) {
+      return 32;
+   }
+
+   /* Same data items, but added in a different order */
+      QCBOREncode_Init(&EC, TestBuf);
+      QCBOREncode_OpenMap(&EC);
+        QCBOREncode_AddBoolToMap(&EC, "boo", true);
+        QCBOREncode_OpenMapInMapN(&EC, 428);
+          QCBOREncode_OpenMapInMap(&EC, "empty1");
+            QCBOREncode_CloseAndSortMap(&EC);
+          QCBOREncode_OpenArrayInMap(&EC, "array");
+            QCBOREncode_AddSZString(&EC, "hi");
+            QCBOREncode_AddSZString(&EC, "there");
+            QCBOREncode_CloseArray(&EC);
+          QCBOREncode_OpenMapInMap(&EC, "empty2");
+            QCBOREncode_CloseAndSortMap(&EC);
+          QCBOREncode_AddNULLToMap(&EC, "null");
+          QCBOREncode_CloseAndSortMap(&EC);
+        QCBOREncode_AddDateEpochToMapN(&EC, 88, 888888);
+        QCBOREncode_AddInt64ToMap(&EC, "three", 3);
+        QCBOREncode_CloseAndSortMap(&EC);
+      uErr = QCBOREncode_Finish(&EC, &EncodedAndSorted);
+      if(uErr) {
+         return 31;
+      }
+
+      if(UsefulBuf_CompareWithDiagnostic(EncodedAndSorted,
+                                         UsefulBuf_FROM_BYTE_ARRAY_LITERAL(spNested),
+                                         &CompareDiagnostics)) {
+         return 32;
+      }
+
+
+
+
+
    /* --- Degenerate case of everything in order --- */
    QCBOREncode_Init(&EC, TestBuf);
    QCBOREncode_OpenMap(&EC);
@@ -3393,5 +3493,29 @@
       return 114;
    }
 
+   QCBOREncode_Init(&EC, TestBuf);
+   QCBOREncode_OpenMap(&EC);
+   QCBOREncode_AddInt64ToMapN(&EC, 3, 3);
+   QCBOREncode_AddInt64ToMapN(&EC, 1, 1);
+   QCBOREncode_AddInt64ToMapN(&EC, 1, 2);
+   QCBOREncode_AddInt64ToMapN(&EC, 2, 2);
+   QCBOREncode_CloseAndSortMap(&EC);
+   uErr = QCBOREncode_Finish(&EC, &EncodedAndSorted);
+   if(uErr != QCBOR_ERR_DUPLICATE_LABEL) {
+      return 115;
+   }
+
+   QCBOREncode_Init(&EC, TestBuf);
+   QCBOREncode_OpenMap(&EC);
+   QCBOREncode_AddInt64ToMap(&EC, "abc", 3);
+   QCBOREncode_AddInt64ToMap(&EC, "def", 1);
+   QCBOREncode_AddInt64ToMap(&EC, "def", 1);
+   QCBOREncode_AddInt64ToMap(&EC, "def", 2);
+   QCBOREncode_CloseAndSortMap(&EC);
+   uErr = QCBOREncode_Finish(&EC, &EncodedAndSorted);
+   if(uErr != QCBOR_ERR_DUPLICATE_LABEL) {
+      return 116;
+   }
+
    return 0;
 }