Is "/usr/bin/sort -u" really so dumb as to sort all of the duplicates and then only eliminate them at the end?

Yes.

The 17 second difference between sorting 10e6 records containing just 100 values, with & without -u, is all down to only having to write 100 records to the final output file.

If it were only sorting 100 records, it would take far less time.

C:\test>perl -E"say int( rand 100 ) for 1 .. 10e6" > 10e6(of100).dat

C:\test>timeit \perl64\bin\sort.exe -u -o sorted "10e6(of100).dat"
Took: 70.141548560 seconds

C:\test>timeit \perl64\bin\sort.exe -o sorted "10e6(of100).dat"
Took: 87.626558680 seconds
[download]

The salient sub mergefps() (called from merge(), called from sort(), called from main()) is:

static void
mergefps (char **files, register int nfiles,
      FILE *ofp, const char *output_file)
{
  FILE *fps[NMERGE];        /* Input streams for each file.  */
  struct buffer buffer[NMERGE];    /* Input buffers for each file. */
  struct line saved;        /* Saved line storage for unique check. */
  struct line const *savedline = NULL;
                /* &saved if there is a saved line. */
  size_t savealloc = 0;        /* Size allocated for the saved line. *
+/
  struct line const *cur[NMERGE]; /* Current line in each line table. 
+*/
  struct line const *base[NMERGE]; /* Base of each line table.  */
  int ord[NMERGE];        /* Table representing a permutation of fps,
                   such that cur[ord[0]] is the smallest line
                   and will be next output. */
  register int i, j, t;
  struct keyfield *key = keylist;
  saved.text = NULL;

  /* Read initial lines from each input file. */
  for (i = 0; i < nfiles; )
    {
      fps[i] = xfopen (files[i], "r");
      initbuf (&buffer[i], sizeof (struct line),
           MAX (merge_buffer_size, sort_size / nfiles));
      if (fillbuf (&buffer[i], fps[i], files[i]))
    {
      struct line const *linelim = buffer_linelim (&buffer[i]);
      cur[i] = linelim - 1;
      base[i] = linelim - buffer[i].nlines;
      i++;
    }
      else
    {
      /* fps[i] is empty; eliminate it from future consideration.  */
      xfclose (fps[i], files[i]);
      zaptemp (files[i]);
      free (buffer[i].buf);
      --nfiles;
      for (j = i; j < nfiles; ++j)
        files[j] = files[j + 1];
    }
    }

  if (! ofp)
    ofp = xfopen (output_file, "w");

  /* Set up the ord table according to comparisons among input lines.
     Since this only reorders two items if one is strictly greater tha
+n
     the other, it is stable. */
  for (i = 0; i < nfiles; ++i)
    ord[i] = i;
  for (i = 1; i < nfiles; ++i)
    if (0 < compare (cur[ord[i - 1]], cur[ord[i]]))
      t = ord[i - 1], ord[i - 1] = ord[i], ord[i] = t, i = 0;

  /* Repeatedly output the smallest line until no input remains. */
  while (nfiles)
    {
      struct line const *smallest = cur[ord[0]];

      /* If uniquified output is turned on, output only the first of
     an identical series of lines. */
      if (unique)
[download]