Index: libiberty/ChangeLog
===================================================================
--- libiberty/ChangeLog	(revision 213873)
+++ libiberty/ChangeLog	(working copy)
@@ -1,3 +1,10 @@
+2014-08-12  Felix Yang  <fei.yang0953@gmail.com>
+
+	* qsort.c: New file.
+	* Makefile.in (CFILES): Add qsort.c
+	(REQUIRED_OFILES): Add qsort.o.
+	(qsort.o): New target.
+
 2014-06-11  Andrew Burgess  <aburgess@broadcom.com>
 
 	* cplus-dem.c (do_type): Call string_delete even if the call to
Index: libiberty/qsort.c
===================================================================
--- libiberty/qsort.c	(revision 0)
+++ libiberty/qsort.c	(revision 0)
@@ -0,0 +1,178 @@
+/*
+ * Copyright (c) 1992, 1993
+ *	The Regents of the University of California.  All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ * 3. All advertising materials mentioning features or use of this software
+ *    must display the following acknowledgement:
+ *	This product includes software developed by the University of
+ *	California, Berkeley and its contributors.
+ * 4. Neither the name of the University nor the names of its contributors
+ *    may be used to endorse or promote products derived from this software
+ *    without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+
+#include <stdlib.h>
+
+#define min(a, b)	(a) < (b) ? a : b
+
+/*
+ * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function".
+ */
+#define swapcode(TYPE, parmi, parmj, n)		\
+{						\
+  long i = (n) / sizeof (TYPE); 		\
+  TYPE *pi = (TYPE *) (parmi);			\
+  TYPE *pj = (TYPE *) (parmj);			\
+  do { 						\
+    TYPE t = *pi;				\
+    *pi++ = *pj;				\
+    *pj++ = t;					\
+  } while (--i > 0);				\
+}
+
+#define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \
+	es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1;
+
+static inline void
+swapfunc (char *a, char *b, int n, int swaptype)
+{
+  if (swaptype <= 1) 
+    swapcode (long, a, b, n)
+  else
+    swapcode (char, a, b, n)
+}
+
+#define swap(a, b)					\
+	if (swaptype == 0) {				\
+		long t = *(long *)(a);			\
+		*(long *)(a) = *(long *)(b);		\
+		*(long *)(b) = t;			\
+	} else						\
+		swapfunc(a, b, es, swaptype)
+
+#define vecswap(a, b, n) 	if ((n) > 0) swapfunc (a, b, n, swaptype)
+
+static inline char *
+med3 (char *a, char *b, char *c, int (*cmp)())
+{
+  return cmp (a, b) < 0 ?
+           (cmp (b, c) < 0 ? b : (cmp (a, c) < 0 ? c : a))
+           : (cmp (b, c) > 0 ? b : (cmp (a, c) < 0 ? a : c));
+}
+
+void
+qsort (void *a, size_t n, size_t es, int (*cmp)())
+{
+  char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
+  int d, r, swaptype, swap_cnt;
+
+loop:
+  SWAPINIT (a, es);
+  swap_cnt = 0;
+  if (n < 7)
+    {
+      for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es)
+        for (pl = pm; pl > (char *) a && cmp (pl - es, pl) > 0; pl -= es)
+          swap (pl, pl - es);
+      return;
+    }
+
+  pm = (char *) a + (n / 2) * es;
+  if (n > 7)
+    {
+      pl = a;
+      pn = (char *) a + (n - 1) * es;
+      if (n > 40)
+        {
+          d = (n / 8) * es;
+          pl = med3 (pl, pl + d, pl + 2 * d, cmp);
+          pm = med3 (pm - d, pm, pm + d, cmp);
+          pn = med3 (pn - 2 * d, pn - d, pn, cmp);
+        }
+      pm = med3 (pl, pm, pn, cmp);
+    }
+
+  swap (a, pm);
+  pa = pb = (char *) a + es;
+
+  pc = pd = (char *) a + (n - 1) * es;
+  for (;;)
+    {
+      while (pb <= pc && (r = cmp (pb, a)) <= 0)
+        {
+          if (r == 0)
+            {
+              swap_cnt = 1;
+              swap (pa, pb);
+              pa += es;
+            }
+          pb += es;
+        }
+
+      while (pb <= pc && (r = cmp (pc, a)) >= 0)
+        {
+          if (r == 0)
+            {
+              swap_cnt = 1;
+              swap (pc, pd);
+              pd -= es;
+            }
+          pc -= es;
+        }
+
+      if (pb > pc)
+        break;
+
+      swap (pb, pc);
+      swap_cnt = 1;
+      pb += es;
+      pc -= es;
+    }
+
+  if (swap_cnt == 0)
+    {
+      /* Switch to insertion sort.  */
+      for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es)
+        for (pl = pm; pl > (char *) a && cmp (pl - es, pl) > 0; pl -= es)
+          swap (pl, pl - es);
+      return;
+    }
+
+  pn = (char *) a + n * es;
+  r = min (pa - (char *)a, pb - pa);
+  vecswap (a, pb - r, r);
+  r = min (pd - pc, pn - pd - es);
+  vecswap (pb, pn - r, r);
+
+  if ((r = pb - pa) > es)
+    qsort (a, r / es, es, cmp);
+
+  if ((r = pd - pc) > es)
+    { 
+      /* Iterate rather than recurse to save stack space.  */
+      a = pn - r;
+      n = r / es;
+      goto loop;
+    }
+}
Index: libiberty/Makefile.in
===================================================================
--- libiberty/Makefile.in	(revision 213873)
+++ libiberty/Makefile.in	(working copy)
@@ -143,7 +143,7 @@ CFILES = alloca.c argv.c asprintf.c atexit.c				\
 	partition.c pexecute.c						\
 	 pex-common.c pex-djgpp.c pex-msdos.c pex-one.c			\
 	 pex-unix.c pex-win32.c						\
-         physmem.c putenv.c						\
+         physmem.c putenv.c qsort.c					\
 	random.c regex.c rename.c rindex.c				\
 	safe-ctype.c setenv.c setproctitle.c sha1.c sigsetmask.c        \
 	 simple-object.c simple-object-coff.c simple-object-elf.c	\
@@ -180,7 +180,7 @@ REQUIRED_OFILES =							\
 	./obstack.$(objext)						\
 	./partition.$(objext) ./pexecute.$(objext) ./physmem.$(objext)	\
 	./pex-common.$(objext) ./pex-one.$(objext)			\
-	./@pexecute@.$(objext)						\
+	./@pexecute@.$(objext) ./qsort.$(objext)				\
 	./safe-ctype.$(objext)						\
 	./simple-object.$(objext) ./simple-object-coff.$(objext)	\
 	./simple-object-elf.$(objext) ./simple-object-mach-o.$(objext)	\
@@ -1139,6 +1139,15 @@ $(CONFIGURED_OFILES): stamp-picdir stamp-noasandir
 	else true; fi
 	$(COMPILE.c) $(srcdir)/putenv.c $(OUTPUT_OPTION)
 
+./qsort.$(objext): $(srcdir)/qsort.c $(INCDIR)/ansidecl.h
+	if [ x"$(PICFLAG)" != x ]; then \
+	  $(COMPILE.c) $(PICFLAG) $(srcdir)/qsort.c -o pic/$@; \
+	else true; fi
+	if [ x"$(NOASANFLAG)" != x ]; then \
+ 	  $(COMPILE.c) $(PICFLAG) $(NOASANFLAG) $(srcdir)/qsort.c -o noasan/$@; \
+	else true; fi
+	  $(COMPILE.c) $(srcdir)/qsort.c $(OUTPUT_OPTION)
+
 ./random.$(objext): $(srcdir)/random.c $(INCDIR)/ansidecl.h
 	if [ x"$(PICFLAG)" != x ]; then \
 	  $(COMPILE.c) $(PICFLAG) $(srcdir)/random.c -o pic/$@; \
