Index: sys/netinet/tcp_lro.h
===================================================================
--- sys/netinet/tcp_lro.h
+++ sys/netinet/tcp_lro.h
@@ -38,8 +38,8 @@
 #define	TCP_LRO_ENTRIES	8
 #endif
 
-#define	TCP_LRO_SEQUENCE(mb) \
-    (mb)->m_pkthdr.PH_loc.thirtytwo[0]
+#define	TCP_LRO_SEQUENCE_U64(mb) \
+    (mb)->m_pkthdr.PH_loc.sixtyfour[0]
 
 struct lro_entry {
 	LIST_ENTRY(lro_entry)	next;
Index: sys/netinet/tcp_lro.c
===================================================================
--- sys/netinet/tcp_lro.c
+++ sys/netinet/tcp_lro.c
@@ -365,25 +365,94 @@
 	LIST_INSERT_HEAD(&lc->lro_free, le, next);
 }
 
-static int
-tcp_lro_mbuf_compare_header(const void *ppa, const void *ppb)
+static inline uint64_t
+tcp_lro_msb_64(uint64_t x)
+{
+	x |= (x >> 1);
+	x |= (x >> 2);
+	x |= (x >> 4);
+	x |= (x >> 8);
+	x |= (x >> 16);
+	x |= (x >> 32);
+	return (x & ~(x >> 1));
+}
+
+/*
+ * The tcp_lro_sort() routine is comparable to qsort(), except it has
+ * a worst case complexity limit of O(MIN(N,64)*N), where N is the
+ * number of elements to sort and 64 is the number of hash bits
+ * available.
+ */
+static void
+tcp_lro_sort(struct mbuf **parray, uint32_t size)
 {
-	const struct mbuf *ma = *((const struct mbuf * const *)ppa);
-	const struct mbuf *mb = *((const struct mbuf * const *)ppb);
-	int ret;
+	uint64_t ones;
+	uint64_t zeros;
+	uint32_t limit;
+	uint32_t x;
+	uint32_t y;
 
-	ret = M_HASHTYPE_GET(ma) - M_HASHTYPE_GET(mb);
-	if (ret != 0)
-		goto done;
+repeat:
+	if (size <= 1)
+		return;
+
+	/* scan all hash values for set and cleared bits */
+	ones = 0;
+	zeros = 0;
+	for (x = 0; x != size; x++) {
+		ones |= TCP_LRO_SEQUENCE_U64(parray[x]);
+		zeros |= ~TCP_LRO_SEQUENCE_U64(parray[x]);
+	}
+
+	/* check if all are same value */
+	ones &= zeros;
+	if (ones == 0)
+		return;
+
+	/* compute bit-mask */
+	ones = tcp_lro_msb_64(ones);
 
-	if (ma->m_pkthdr.flowid > mb->m_pkthdr.flowid)
-		return (1);
-	else if (ma->m_pkthdr.flowid < mb->m_pkthdr.flowid)
-		return (-1);
+	/* compute how many zeros are in our set */
+	for (limit = x = 0; x != size; x++) {
+		if (!(TCP_LRO_SEQUENCE_U64(parray[x]) & ones))
+			limit++;
+	}
+
+	/* sanity check */
+	if (limit == 0 || limit == size)
+		return;
 
-	ret = TCP_LRO_SEQUENCE(ma) - TCP_LRO_SEQUENCE(mb);
+	x = 0;
+	y = limit;
+
+	while (1) {
+		struct mbuf *temp;
+
+		/* find next misplaced cleared bit */
+		while (TCP_LRO_SEQUENCE_U64(parray[y]) & ones) {
+			if (++y == size)
+				goto done;
+		}
+
+		/* find next misplaced set bit */
+		while (!(TCP_LRO_SEQUENCE_U64(parray[x]) & ones)) {
+			if (++x == limit)
+				goto done;
+		}
+
+		/* swap */
+		temp = parray[x];
+		parray[x] = parray[y];
+		parray[y] = temp;
+	}
 done:
-	return (ret);
+	/* sort zeros */
+	tcp_lro_sort(parray, limit);
+
+	/* sort ones */
+	parray += limit;
+	size -= limit;
+	goto repeat;
 }
 
 void
@@ -398,8 +467,7 @@
 		goto done;
 
 	/* sort all mbufs according to stream */
-	qsort(lc->lro_mbuf_data, lc->lro_mbuf_count, sizeof(struct mbuf *),
-	    &tcp_lro_mbuf_compare_header);
+	tcp_lro_sort(lc->lro_mbuf_data, lc->lro_mbuf_count);
 
 	/* input data into LRO engine, stream by stream */
 	flowid = 0;
@@ -420,7 +488,7 @@
 		}
 #ifdef TCP_LRO_RESET_SEQUENCE
 		/* reset sequence number */
-		TCP_LRO_SEQUENCE(mb) = 0;
+		TCP_LRO_SEQUENCE_U64(mb) = 0;
 #endif
 		/* add packet to LRO engine */
 		if (tcp_lro_rx(lc, mb, 0) != 0) {
@@ -799,8 +867,11 @@
 	if (__predict_false(lc->lro_mbuf_count == lc->lro_mbuf_max))
 		tcp_lro_flush_all(lc);
 
-	/* store sequence number */
-	TCP_LRO_SEQUENCE(mb) = lc->lro_mbuf_count;
+	/* create sequence number */
+	TCP_LRO_SEQUENCE_U64(mb) =
+	    (((uint64_t)M_HASHTYPE_GET(mb)) << 56) |
+	    (((uint64_t)mb->m_pkthdr.flowid) << 24) |
+	    ((uint64_t)lc->lro_mbuf_count);
 
 	/* enter mbuf */
 	lc->lro_mbuf_data[lc->lro_mbuf_count++] = mb;