Re: [PATCH] Use a heap for the internal merge.

[Pádraig Brady]

I notice this uses C99 syntax like: for (size_t i; ...
There is precedent in remove.c (sep 2008) for that so I thinks it's fine.

Note I noticed some good info on heaps and sorts in this output:
echo "import heapq; print heapq.__about__" | python

So I think this patch is a fine improvement and should
be pushed with the following tweaks...

@@ -1,30 +1,35 @@
 From: Paul Eggert <address@hidden>
 Date: Fri, 13 Mar 2009 12:24:22 -0700
-Subject: [PATCH] Use a heap for the internal merge.
+Subject: [PATCH] sort: Use a heap to speed up the internal merge

-With random data and a 64-way merge this sped up 'sort' by 5% on our
-tests.  Sorry, I don't know how to put multiple authors in the patch.
-However, the authors are:
-
-Alexander Nguyen <address@hidden>
-Paul Eggert <address@hidden>
-
-We've both signed papers.
-
------
-
-src/sort.c (mergefps): When merging a line with a K-way merge, update a
-heap rather than doing a linear insertion.  This improves the
-overall performance of 'sort' from O(N*K) to O(N log K).
+* src/sort.c (mergefps): When merging a line with a K-way merge, update
+a heap rather than doing a linear insertion.  This improves the overall
+performance of 'sort' from O(N*K) to O(N log K), which in testing with
+random data and 64-way merge sped up 'sort' by 5%.
 (less_than, swap): New functions.
 (sortlines_temp): Rename local variable so that it doesn't shadow the
 new 'swap' function.
+* THANKS: Add Alexander Nguyen who coauthored this commit.
 ---
+ THANKS     |    1 +
  src/sort.c |  140 +++++++++++++++++++++++++++++-------------------------------
- 1 files changed, 67 insertions(+), 73 deletions(-)
+ 2 files changed, 68 insertions(+), 73 deletions(-)

+diff --git a/THANKS b/THANKS
+index 46d077b..55f0035 100644
+--- a/THANKS
++++ b/THANKS
+@@ -23,6 +23,7 @@ Alberto Accomazzi                   address@hidden
+ aldomel                             address@hidden
+ Alen Muzinic                        address@hidden
+ Alexander V. Lukyanov               address@hidden
++Alexander Nguyen                    address@hidden
+ Allen Hewes                         address@hidden
+ Axel Dörfler                        address@hidden
+ Alexandre Duret-Lutz                address@hidden
 diff --git a/src/sort.c b/src/sort.c
-index 7b0b064..0e22aff 100644
+index 7b0b064..ab80e14 100644
 --- a/src/sort.c
 +++ b/src/sort.c
 @@ -2060,6 +2060,25 @@ compare (const struct line *a, const struct line *b)
@@ -32,7 +37,7 @@
  }

 +/* If CUR is a vector of lines, and ORD a vector of indexes into CUR,
-+   then return true if the line ORD[A] less less than the line ORD[B]
++   then return true if the line ORD[A] is less than the line ORD[B]
 +   in CUR, using a stable comparison.  */
 +static bool
 +less_than (struct line const *const *cur, size_t const *ord,