From ad9438bd0a646c5b6e8197b7cd96736f5660bbe8 Mon Sep 17 00:00:00 2001
From: Ulya Trofimovich <skvadrik@gmail.com>
Date: Fri, 8 Feb 2019 15:25:54 +0000
Subject: [PATCH] Use insertion sort instead of bubble sort (it is slightly
 faster).

---
 re2c/src/dfa/find_state.cc | 20 +++++++++++---------
 1 file changed, 11 insertions(+), 9 deletions(-)

diff --git a/re2c/src/dfa/find_state.cc b/re2c/src/dfa/find_state.cc
index 1b6bfaa8..f8892f04 100644
--- a/re2c/src/dfa/find_state.cc
+++ b/re2c/src/dfa/find_state.cc
@@ -373,16 +373,18 @@ bool equal_lookahead_tags(determ_context_t &ctx
 
 void group_by_tag(tag_path_t &p)
 {
-    // a variant of bubble sort
-    for (size_t n = p.size(); n > 1; ) {
-        size_t m = 0;
-        for (size_t i = 1; i < n; ++i) {
-            if (p[i - 1].idx > p[i].idx) {
-                std::swap(p[i - 1], p[i]);
-                m = i;
-            }
+    // insertion sort (must be careful to preserve order of elements
+    // with the same tag, but different negative bit)
+    size_t i, j, n = p.size();
+
+    for (i = 1; i < n; ++i) {
+        const tag_info_t info = p[i];
+        const size_t tag = info.idx;
+
+        for (j = i; j > 0 && p[j - 1].idx > tag; --j) {
+            p[j] = p[j - 1];
         }
-        n = m;
+        p[j] = info;
     }
 }
 
-- 
2.40.0