diff --git a/src/tree_data.c b/src/tree_data.c
index 782b118..faeae00 100644
--- a/src/tree_data.c
+++ b/src/tree_data.c
@@ -699,8 +699,13 @@
 lyd_insert_node_last(struct lyd_node *parent, struct lyd_node *first_sibling, struct lyd_node *node)
 {
     if (first_sibling) {
-        assert(!lyds_is_supported(node) || (first_sibling->prev->schema != node->schema) ||
-                lyds_compare_single(node, first_sibling->prev));
+#ifndef NDEBUG
+        if (lyds_is_supported(node) && (first_sibling->prev->schema == node->schema) &&
+                (lyds_compare_single(first_sibling->prev, node) > 0)) {
+            LOGWRN(LYD_CTX(node), "Data in \"%s\" are not sorted, inserted node should not be added to the end.",
+                    node->schema->name);
+        }
+#endif
         lyd_insert_after_node(first_sibling->prev, node);
     } else if (parent) {
         lyd_insert_only_child(parent, node);
diff --git a/src/tree_data_internal.h b/src/tree_data_internal.h
index d3aa1a7..0e0768b 100644
--- a/src/tree_data_internal.h
+++ b/src/tree_data_internal.h
@@ -393,11 +393,8 @@
  * @param[in] parent Parent to insert into, NULL for top-level sibling.
  * @param[in,out] first_sibling First sibling, NULL if no top-level sibling exist yet. Can be also NULL if @p parent is set.
  * @param[in] node Individual node (without siblings) to insert.
- * @param[in] last If set, do not search for the correct anchor but always insert at the end.
- * For (leaf-)lists that have the LYS_ORDBY_SYSTEM flag set, the @p last (due to optimization) causes
- * the sorting tree (lyds_tree) not to be created. However, it is possible to implicitly create
- * the lyds_tree by inserting another node without setting the @p last. After that, the @p last MUST NOT be
- * set for a given (leaf-list) instance, as this will cause the order to be corrupted.
+ * @param[in] last If set, do not search for the correct anchor but always insert at the end. Setting the flag can
+ * break the ordering of nodes for (leaf-)lists that have the LYS_ORDBY_SYSTEM flag set.
  */
 void lyd_insert_node(struct lyd_node *parent, struct lyd_node **first_sibling, struct lyd_node *node, ly_bool last);
 
diff --git a/src/tree_data_sorted.c b/src/tree_data_sorted.c
index 39b16ef..914327a 100644
--- a/src/tree_data_sorted.c
+++ b/src/tree_data_sorted.c
@@ -668,10 +668,12 @@
  *
  * @param[in,out] rbt Root of the Red-black tree. After the @p rbn is inserted, the root may change.
  * @param[in] rbn Node to insert.
+ * @param[out] max_p Set to 1 if the inserted node will also be maximum.
  */
 static void
-rb_insert_node(struct rb_node **rbt, struct rb_node *rbn)
+rb_insert_node(struct rb_node **rbt, struct rb_node *rbn, ly_bool *max_p)
 {
+    ly_bool max;
     struct rb_node *tmp;
     struct rb_node *parent = NULL;
     int comp = 0;
@@ -684,6 +686,7 @@
         rb_compare = rb_compare_lists;
     }
 
+    max = 1;
     tmp = *rbt;
     while (tmp != NULL) {
         parent = tmp;
@@ -691,6 +694,7 @@
         comp = rb_compare(RBN_DNODE(tmp), RBN_DNODE(rbn));
         if (comp > 0) {
             tmp = RBN_LEFT(tmp);
+            max = 0;
         } else {
             tmp = RBN_RIGHT(tmp);
         }
@@ -709,6 +713,10 @@
     }
 
     rb_insert_color(rbt, rbn);
+
+    if (max_p) {
+        *max_p = max;
+    }
 }
 
 /**
@@ -932,28 +940,34 @@
 /**
  * @brief Additionally create the Red-black tree for the sorted nodes.
  *
- * @param[in] leader First instance of the (leaf-)list.
+ * @param[in,out] leader First instance of the (leaf-)list.
  * @param[in] root_meta From the @p leader, metadata in which is the root of the Red-black tree.
  * @param[in] rbt From the @p root_meta, root of the Red-black tree.
  * @return LY_ERR value.
  */
 static LY_ERR
-lyds_additionally_create_rb_tree(struct lyd_node *leader, struct lyd_meta *root_meta, struct rb_node **rbt)
+lyds_additionally_create_rb_tree(struct lyd_node **leader, struct lyd_meta *root_meta, struct rb_node **rbt)
 {
     LY_ERR ret;
+    ly_bool max;
     struct rb_node *rbn;
     struct lyd_node *iter;
 
     /* let's begin with the leader */
-    ret = lyds_create_node(leader, &rbn);
+    ret = lyds_create_node(*leader, &rbn);
     LY_CHECK_RET(ret);
     *rbt = rbn;
 
     /* continue with the rest of the nodes */
-    for (iter = leader->next; iter && (iter->schema == leader->schema); iter = iter->next) {
+    for (iter = (*leader)->next; iter && (iter->schema == (*leader)->schema); iter = iter->next) {
         ret = lyds_create_node(iter, &rbn);
         LY_CHECK_RET(ret);
-        rb_insert_node(rbt, rbn);
+        rb_insert_node(rbt, rbn, &max);
+        if (!max) {
+            /* nodes were not sorted, they will be sorted now */
+            lyd_unlink_ignore_lyds(iter);
+            lyds_link_data_node(leader, iter, root_meta, rbn);
+        }
     }
 
     /* store pointer to the root */
@@ -1019,7 +1033,7 @@
     LY_CHECK_RET(ret);
 
     /* insert red-black node with @p node to the Red-black tree */
-    rb_insert_node(rbt, *rbn);
+    rb_insert_node(rbt, *rbn, NULL);
 
     return LY_SUCCESS;
 }
@@ -1052,7 +1066,7 @@
          * created additionally now. It may still not be worth creating a tree and it may be better
          * to insert the node by linear search instead, but that is a case for further optimization.
          */
-        ret = lyds_additionally_create_rb_tree(*leader, root_meta, &rbt);
+        ret = lyds_additionally_create_rb_tree(leader, root_meta, &rbt);
         LY_CHECK_RET(ret);
     }
 
@@ -1358,6 +1372,10 @@
     /* move the rest of the source nodes */
     lyds_merge_nodes2_back(dst_iter, next_p);
 
+    if (*next_p && ((*next_p)->schema == (*leader_dst)->schema)) {
+        ret = lyds_merge_nodes1(leader_dst, root_meta_src, rbt_src, *next_p, next_p);
+    }
+
 cleanup:
     RBT_SET(root_meta_src, rbt_src);
 
@@ -1376,8 +1394,9 @@
  * @param[in] root_meta_src Metadata 'lyds_tree' from @p leader_src.
  * @param[in] rbt_src Root of the source Red-black tree.
  * @param[out] next_p Data node located after source (leaf-)list.
+ * @return LY_ERR value.
  */
-static void
+static LY_ERR
 lyds_merge_nodes3(struct lyd_node **leader_dst, struct lyd_meta *root_meta_dst, struct rb_node *rbt_dst,
         struct lyd_meta *root_meta_src, struct rb_node *rbt_src, struct lyd_node **next_p)
 {
@@ -1393,13 +1412,19 @@
         node = RBN_DNODE(iter);
         *next_p = node->next;
         RBN_RESET(iter, node);
-        rb_insert_node(&rbt_dst, iter);
+        rb_insert_node(&rbt_dst, iter, NULL);
         lyd_unlink_ignore_lyds(node);
         lyds_link_data_node(leader_dst, node, root_meta_dst, iter);
         lyd_insert_hash(node);
     }
 
-    RBT_SET(root_meta_dst, rbt_dst);
+    if (!*next_p || ((*next_p)->schema != (*leader_dst)->schema)) {
+        RBT_SET(root_meta_dst, rbt_dst);
+    } else {
+        LY_CHECK_RET(lyds_merge_nodes1(leader_dst, root_meta_dst, rbt_dst, *next_p, next_p));
+    }
+
+    return LY_SUCCESS;
 }
 
 LY_ERR
@@ -1422,7 +1447,7 @@
     if (!rbt_dst && !rbt_src) {
         /* create RB tree from destination nodes, merge and move source nodes */
         LY_CHECK_RET(lyds_create_metadata(*leader_dst, &root_meta_dst));
-        LY_CHECK_RET(lyds_additionally_create_rb_tree(*leader_dst, root_meta_dst, &rbt_dst));
+        LY_CHECK_RET(lyds_additionally_create_rb_tree(leader_dst, root_meta_dst, &rbt_dst));
         ret = lyds_merge_nodes1(leader_dst, root_meta_dst, rbt_dst, leader_src, next_p);
     } else if (rbt_dst && !rbt_src) {
         /* just merge and move source nodes */
diff --git a/tests/utests/data/test_tree_data_sorted.c b/tests/utests/data/test_tree_data_sorted.c
index 8b06f4f..de2f121 100644
--- a/tests/utests/data/test_tree_data_sorted.c
+++ b/tests/utests/data/test_tree_data_sorted.c
@@ -1491,6 +1491,55 @@
     lyd_free_all(cont);
 }
 
+static void
+test_order_violation(void **state)
+{
+    const char *schema, *data;
+    struct lys_module *mod;
+    struct lyd_node *tree, *node, *dst, *first;
+
+    schema = "module a {namespace urn:tests:a;prefix a;yang-version 1.1;revision 2014-05-08;"
+            "leaf-list ll {type uint32;}}";
+    UTEST_ADD_MODULE(schema, LYS_IN_YANG, NULL, &mod);
+
+    /* inserting a new node causes the nodes to be sorted */
+    data = "{\"a:ll\":[1,8,2]}";
+    CHECK_PARSE_LYD_PARAM(data, LYD_JSON, LYD_PARSE_ORDERED, LYD_VALIDATE_PRESENT, LY_SUCCESS, tree);
+    assert_true(tree && !tree->meta && tree->next && tree->next->next);
+    assert_string_equal(lyd_get_value(tree), "1");
+    assert_string_equal(lyd_get_value(tree->next), "8");
+    assert_string_equal(lyd_get_value(tree->next->next), "2");
+#ifndef NDEBUG
+    CHECK_LOG_CTX("Data in \"ll\" are not sorted, inserted node should not be added to the end.", NULL, 0);
+#endif
+    assert_int_equal(lyd_new_term(NULL, mod, "ll", "3", 0, &node), LY_SUCCESS);
+    lyd_insert_sibling(tree, node, NULL);
+    assert_string_equal(lyd_get_value(tree), "1");
+    assert_string_equal(lyd_get_value(tree->next), "2");
+    assert_string_equal(lyd_get_value(tree->next->next), "3");
+    assert_string_equal(lyd_get_value(tree->next->next->next), "8");
+    lyd_free_all(tree);
+
+    /* move unsorted nodes causes the nodes to be sorted */
+    data = "{\"a:ll\":[1,8,2]}";
+    CHECK_PARSE_LYD_PARAM(data, LYD_JSON, LYD_PARSE_ORDERED, LYD_VALIDATE_PRESENT, LY_SUCCESS, tree);
+#ifndef NDEBUG
+    CHECK_LOG_CTX("Data in \"ll\" are not sorted, inserted node should not be added to the end.", NULL, 0);
+#endif
+    data = "{\"a:ll\":[7,5]}";
+    CHECK_PARSE_LYD_PARAM(data, LYD_JSON, LYD_PARSE_ORDERED, LYD_VALIDATE_PRESENT, LY_SUCCESS, dst);
+#ifndef NDEBUG
+    CHECK_LOG_CTX("Data in \"ll\" are not sorted, inserted node should not be added to the end.", NULL, 0);
+#endif
+    lyd_insert_sibling(dst, tree, &first);
+    assert_string_equal(lyd_get_value(first), "1");
+    assert_string_equal(lyd_get_value(first->next), "2");
+    assert_string_equal(lyd_get_value(first->next->next), "5");
+    assert_string_equal(lyd_get_value(first->next->next->next), "7");
+    assert_string_equal(lyd_get_value(first->next->next->next->next), "8");
+    lyd_free_all(first);
+}
+
 int
 main(void)
 {
@@ -1530,6 +1579,7 @@
         UTEST(test_move_part_list),
         UTEST(test_merge_whole_list),
         UTEST(test_unlink_siblings),
+        UTEST(test_order_violation),
     };
 
     return cmocka_run_group_tests(tests, NULL, NULL);