From e567c8ccb4fb1e51af5c94346b614851af19fb07 Mon Sep 17 00:00:00 2001
From: Andres Mejia <amejia004@gmail.com>
Date: Sat, 9 Feb 2013 22:09:30 -0500
Subject: [PATCH] Redo the strings sorting function, allocate/free memory as
 needed. This is the normal implementation of quicksort.

---
 libarchive/archive_util.c | 54 +++++++++++++++++++++++++++++----------
 1 file changed, 40 insertions(+), 14 deletions(-)

diff --git a/libarchive/archive_util.c b/libarchive/archive_util.c
index 57db5a654..0d6140774 100644
--- a/libarchive/archive_util.c
+++ b/libarchive/archive_util.c
@@ -508,29 +508,55 @@ __archive_ensure_cloexec_flag(int fd)
 static int
 archive_utility_string_sort_helper(char **strings, unsigned int n)
 {
-  unsigned int i, j, pivot;
-  char *tmp;
+  unsigned int i, lesser_count, greater_count;
+  char **lesser, **greater, **tmp, *pivot;
+  int retval1, retval2;
 
+  /* A list of 0 or 1 elements is already sorted */
   if (n <= 1)
     return (ARCHIVE_OK);
 
-  pivot = 0;
+  lesser_count = greater_count = 0;
+  lesser = greater = NULL;
+  pivot = strings[0];
   for (i = 1; i < n; i++)
   {
-    if (strcmp(strings[i], strings[pivot]) < 0)
+    if (strcmp(strings[i], pivot) < 0)
     {
-      tmp = strings[i];
-      for (j = i; j > pivot; j--)
-      {
-        strings[j] = strings[j - 1];
-      }
-      strings[pivot] = tmp;
-      pivot++;
+      lesser_count++;
+      tmp = (char **)realloc(lesser, lesser_count * sizeof(char *));
+      if (!tmp)
+        return (ARCHIVE_FATAL);
+      lesser = tmp;
+      lesser[lesser_count - 1] = strings[i];
+    }
+    else
+    {
+      greater_count++;
+      tmp = (char **)realloc(greater, greater_count * sizeof(char *));
+      if (!tmp)
+        return (ARCHIVE_FATAL);
+      greater = tmp;
+      greater[greater_count - 1] = strings[i];
     }
   }
-  archive_utility_string_sort_helper(strings, pivot + 1);
-  archive_utility_string_sort_helper(strings + pivot + 1, n - (pivot + 1));
-  return (ARCHIVE_OK);
+
+  /* quicksort(lesser) */
+  retval1 = archive_utility_string_sort_helper(lesser, lesser_count);
+  for (i = 0; i < lesser_count; i++)
+    strings[i] = lesser[i];
+  free(lesser);
+
+  /* pivot */
+  strings[lesser_count] = pivot;
+
+  /* quicksort(greater) */
+  retval2 = archive_utility_string_sort_helper(greater, greater_count);
+  for (i = 0; i < greater_count; i++)
+    strings[lesser_count + 1 + i] = greater[i];
+  free(greater);
+
+  return (retval1 < retval2) ? retval1 : retval2;
 }
 
 int
-- 
2.47.2