sort command adds/removes data at will

Question

I'm using sort command to sort rockyou.txt wordlist, which I downloaded from this site:

% sort rockyou.txt > rockyou_sorted.txt

However, when I then check the file sizes of both files, they differ, the sorted file is smaller:

% du -shk rockyou_sorted.txt rockyou.txt 
147520  rockyou_sorted.txt
148304  rockyou.txt

What is interesting is that when I repeat these same steps with clean version of rockyou.txt wordlist, downloaded from here, I get opposite results, that is, the sorted file is bigger:

% sort rockyou_cleaned.txt > rockyou_cleaned_sorted.txt
% du -shk rockyou_cleaned_sorted.txt rockyou_cleaned.txt 
114752  rockyou_cleaned_sorted.txt
102104  rockyou_cleaned.txt

I wonder why is that? Could someone explain it for me, please? Am I doing something wrong? I think both files, the sorted one and the original should be of the same size, shouldn't they?

UPDATE 1, as per Francesco Lucianò's comment below: using this sort command with -o parameter

% sort rockyou.txt -o rockyou_sorted_sO.txt
% du -shk rockyou_sorted_sO.txt rockyou.txt
147996 /Users/Martin/Downloads/rockyou_sorted_sO.txt
148304 /Users/Martin/Downloads/rockyou.txt

The sorted file is still smaller than the original but not that much as when I was using my version of sort command above.

The number of lines is the same in all of the files:

% wc -l rockyou_sorted_sO.txt rockyou_sorted.txt rockyou.txt
14344391 rockyou_sorted_sO.txt
14344391 rockyou_sorted.txt
14344391 rockyou.txt
43033173 total 

UPDATE 2, as per bey0nd's comments below: set | grep LANG outputs nothing at all:

% set | grep LANG
%

% chardet rockyou* 
zsh: command not found: chardet
% uchardet rockyou*
rockyou.txt: UTF-8
rockyou_sorted.txt: UTF-8
rockyou_sorted_duplicut.txt: UTF-8
rockyou_sorted_sO.txt: UTF-8

UPDATE 3, as per steeldriver's comment below:

% system_profiler SPSoftwareDataType
Software:

    System Software Overview:

      System Version: macOS 10.15.4 (19E287)
      Kernel Version: Darwin 19.4.0
      Boot Volume: Macintosh HD
      Boot Mode: Normal
      Computer Name: *REDACTED* MacBook Pro
      User Name: *REDACTED*
      Secure Virtual Memory: Enabled
      System Integrity Protection: Enabled
      Time since boot: 6 days 4:57

The filesystem is APFS.

UPDATE 4, as per roaima's comments below:

% ls -l rockyou*
-rw-r--r--@ 1 **REDACTED**  staff  139921497 May 16 12:24 rockyou.txt
-rw-r--r--  1 **REDACTED**  staff  139921847 May 16 12:25 rockyou_sorted.txt
-rw-r--r--  1 **REDACTED**  staff  139919642 May 16 12:29 rockyou_sorted_duplicut.txt
-rw-r--r--  1 **REDACTED**  staff  139921847 May 16 13:19 rockyou_sorted_sO.txt

% stat -f .
.

UPDATE 5, as per Isaac's comments below:

% head -n3 rockyou.txt | od -An -tcx1 
           1   2   3   4   5   6  \n   1   2   3   4   5  \n   1   2   3
           31  32  33  34  35  36  0a  31  32  33  34  35  0a  31  32  33
           4   5   6   7   8   9  \n                                    
           34  35  36  37  38  39  0a 

% LC_ALL=C sort rockyou.txt >rockyou_sorted_with_LC.txt
% du -shk rockyou_sorted_with_LC.txt rockyou.txt
147520  rockyou_sorted_with_LC.txt
140476  rockyou.txt
% wc -l rockyou_sorted_with_LC.txt rockyou.txt
 14344391 rockyou_sorted_with_LC.txt
 14344391 rockyou.txt
 28688782 total

UPDATE 6, as per fra-san's comment below:

% sort --version
2.3-Apple (101.40.1)
% locale        
LANG=""
LC_COLLATE="en_US.UTF-8"
LC_CTYPE="en_US.UTF-8"
LC_MESSAGES="en_US.UTF-8"
LC_MONETARY="en_US.UTF-8"
LC_NUMERIC="en_US.UTF-8"
LC_TIME="en_US.UTF-8"
LC_ALL="en_US.UTF-8"

Answer 1

There are two things happening here, and they work somewhat counter to each other.

1. The input file is not consistently encoded, and is transformed by sort into valid UTF-8. This makes the file bigger. This affects the ls -l-reported size.
2. Something odd happens with the filesystem storage, which varies the number of blocks used by equal-sized files depending on how they are created. This affects the du -shk-reported size and mostly makes it smaller (but can go either way).

I can give a more exact explanation of the first point than the second, though the short answer is that du is not the right tool to measure individual file sizes, especially on APFS.

The next two sections get well into the weeds of both factors.

---

For factor (1), the file contains lines that are not UTF-8 encoded, which is the default locale encoding on macOS. The sort command modifies these badly-encoded lines when it outputs them, making the file larger. We will investigate that further below, but that's the short answer and you can skip to the next section if that's enough.

If we sort the provided file in the C locale, and then again in the en_US.UTF-8 locale, the two files have different actual sizes:

139921497 rockyou.txt
139921497 rockyou_c.txt
139921847 rockyou_sorted.txt

The first difference between the C- and UTF-8-sorted files is

299c299
<  �R3CKL3$$�
---
>  R3CKL3$$

The first line contains bytes 0x93 and 0x94 at the start and end of the password, which are not valid standalone bytes in UTF-8 (they can only appear as continuation bytes of a multi-byte character). The second contains the Unicode codepoints U+0093 and U+0094, encoded as two bytes of UTF-8 each, C2 93 and C2 94.

The result is that the original ten-byte line is written out as a twelve-byte line. Across the whole file, these changes add up to 350 additional bytes in the sorted file than the original.

What I believe has happened here is:

1. The original line was “R3CKL3$$” (quotes included), encoded in the Windows-1252 codepage (cp1252). The paired quotes are 0x93 and 0x94 in that encoding.
2. It was added to this collection as raw bytes, without any consideration of encoding, as were many other entries.
3. In true Latin-1 ISO 8859-1, the byte range 0x80-0x9f is unoccupied, but in ISO-8859-1 (note extra hyphen) it is filled by the C1 control characters.
4. All of ISO-8859-1 is encoded as the block "Latin-1 Supplement" in Unicode, with codepoints corresponding to the raw byte values and represented by multi-byte encodings C2 80 through C2 BF and C3 80 through C3 BF in UTF-8.
5. macOS sort interprets lone continuation bytes as attempted ISO-8859-1, and internally translates them to Unicode strings in that fashion for sorting: byte 0x93 becomes U+0093 in the string that is sorted.
6. These translated strings are outputted, in UTF-8, instead of the original lines from the file.

Other questions on the site discuss how to fix a misencoded cp1252 file after the fact, if that's something you need.

POSIX notes that in the case that lines contain byte sequences that do not form valid characters in the locale, the utility's behaviour is undefined, so this is strictly allowed by the standard and is not a conformance bug. It's still at the least unexpected and arguably a behavioural bug. Other implementations of sort that I've tried do not behave in this way.

This factor pushes for the file to become slightly larger when you sort it, and truly larger - if you read from the file, you will get more bytes.

---

Factor (2) overall pushes for the file to become "smaller", but that's somewhat of an illusion. Reading the file won't necessarily produce more or fewer bytes just because du says they're different sizes.

du -shk is, in general, not an appropriate way to check file sizes, because

The du utility displays the file system block usage for each file argument

That means it reports information on how much physical space is occupied by the file, rather than its logical size. Depending on the exact parameters of the filesystem and the files in question, the block count could vary quite a lot from what you might expect. There are cases where block counts are useful, like when you're squeezing files onto a full device, but not usually.

One reason block counts are even less useful today is that modern filesystems don't always write data exactly as given: for example, they might silently compress it before storing it to greater or lesser extents, requiring fewer blocks, or leave empty space within blocks to make future insertions easier, using more blocks. Sparse files omit blocks of zeros, but deduplication can go even further than that.

In APFS's case, it suppports compression with several algorithms, some deduplication and delta encoding, encryption, and advanced metadata. Some or all of these may be in play, most likely variations in transparent compression when the file is written, dependent on the application implementation and system load.

If we just cat the file a few times we can see differences already. If I've downloaded rockyou.txt with curl -O then:

• cat rockyou.txt > rockyou2.txt creates a file with the same byte count (139921497) but different block counts for me (147504 for the curl-created one vs 147460 for cat's)
• Catting the new file gives me another block count again (147520), as does cp (150512).
• Running both lines again gives me different results than the first attempt.

I don't know exactly why that is and I'm not sure there's a reasonable way to tell. I suspect it tried harder to compress data some times than others. In all cases, the file is really the same size, and reading from any version returns the same bytes. We just don't get much useful information from the reported block count on APFS or other modern high-performance filesystems. If you're squeezing a file onto a device, trying a few times to get the smallest version may help, but otherwise it's not worth thinking about.

---

Overall, we have an encoding issue that makes the file genuinely slightly larger, counterbalanced by filesystem behaviour that slightly modifies the reported block count of that larger file, making it smaller in your test. A true size measurement shows a consistent increase of 350 bytes upon sorting. Depending on how you look at it, this may be a bug in sort, or it may be a bug in the use of sort by giving it a bad file.