From 1d241bb20053e19359cfa8ec07a99c8efb9120d0 Mon Sep 17 00:00:00 2001
From: Stefan Oberhumer <stefan@obssys.com>
Date: Sat, 2 Oct 2010 00:49:42 +0200
Subject: [PATCH] ntdll: Make NTDLL_mergesort() stable.

---
 dlls/ntdll/misc.c | 10 +++++++---
 1 file changed, 7 insertions(+), 3 deletions(-)

diff --git a/dlls/ntdll/misc.c b/dlls/ntdll/misc.c
index 39b0ad3a762..a2c08c5815e 100644
--- a/dlls/ntdll/misc.c
+++ b/dlls/ntdll/misc.c
@@ -270,9 +270,9 @@ NTDLL_mergesort( void *arr, void *barr, size_t elemsize, int(__cdecl *compar)(co
         for (j=m; j<right; j++)
             memcpy (X(barr,(right+m-j)),X(arr,(j+1)),elemsize);
 
-        for (k=left; k<=right; k++) {
-            /*arr[k]=(barr[i]<barr[j])?barr[i++]:barr[j--];*/
-            if (i != j && compar(X(barr,i),X(barr,j))<0) {
+        /* i=left; j=right; */
+        for (k=left; i<=m && j>m; k++) {
+            if (compar(X(barr,i),X(barr,j))<=0) {
                 memcpy(X(arr,k),X(barr,i),elemsize);
                 i++;
             } else {
@@ -280,6 +280,10 @@ NTDLL_mergesort( void *arr, void *barr, size_t elemsize, int(__cdecl *compar)(co
                 j--;
             }
         }
+        for (; i<=m; i++, k++)
+            memcpy(X(arr,k),X(barr,i),elemsize);
+        for (; j>m; j--, k++)
+            memcpy(X(arr,k),X(barr,j),elemsize);
     }
 #undef X
 }
-- 
2.11.4.GIT