Obviously you want to consolidate fragments. But especially for HDDs there's different tradeoff of placing stuff near the outside compared to towards the center, which also depends on workload ie streaming vs random access, heavy read/write vs mostly read-only.

With PerfectDisk[1] you can decide how you wanted the disk laid out. And it did make a measurable difference in the cases I tested.

For SSDs fragmentation is less of an issue, but it's not completely gone. Especially on Windows with NTFS, where one can run into issues with heavily fragmented files[2][3].

We actually have this very issue with a client in production these days, due to the DB log file causing heavy fragmentation.

[1]: https://www.raxco.com/home/products/perfectdisk-pro

[2]: https://support.microsoft.com/en-us/topic/a-heavily-fragment...

[3]: https://support.assurestor.com/support/solutions/articles/16...

There wasn't just one. Some defrag tools from the days of DOS would actually let you pick. A commonly used one was to try to place the contents of the same directory adjacent to each other on the disk surface, to minimize latency.

I can't remember which it is, but either the center or the outside edge of a disk read faster, so another common trick was to place all the files necessary to boot the system there, to reduce boot times.

Depends on the drive technology. For SSDs you want to avoid extra writes as those wear down the cells. For traditional hard drives you can consolidate empty space to reduce cluster waste, or go for broke and just place everything in order (most fun to watch). Probably the best way would be to group frequently accessed files near each other so the heads traveled less distance.

So far as the algorithm, what I observed is the program would look at how much room was needed to place the next file, then clear that many blocks out of the way by moving them to the end of the drive. Then copy the blocks for the file to form a contiguous stretch of blocks. And repeat. You wanted to have as much free space as the largest file (plus a little), but I think some of them were able to move large files in pieces.

Back in the days of Windows NT we had a network share with 8+ million files on it (a lot for the time) and we had a serious fragmentation problem, where it could take a second or more to read a file. Most of the defraggers just gave up, or weren't making any progress, but we eventually found one that worked (PerfectDisk, maybe?)

Curious too here! I wouldn't be surprised if there was some kind of a dynamic programming algo similar to 0-1 knapsack.

What is being measured?

You've got contiguous space, speed, total time, wear.

Bubble sort obviously.