The Algorithm Behind "Remove Duplicates": Sort-Then-Scan vs Hash-Set, and When Each Is Right

"Remove duplicates" in a sorted list is a different operation than "remove duplicates" in an unsorted list — and which one you need determines whether you have to sort first, which determines whether you can process the data in a single pass

The previous articles on this site covered fuzzy deduplication/record linkage, database-scale deduplication, and GDPR implications. This article addresses the algorithmic side of exact deduplication — the different approaches for finding and removing exact duplicate lines, what their time and memory trade-offs are, and when each matters.

The three fundamental approaches

For exact deduplication of a list of strings (or lines), there are three fundamental algorithmic approaches, each with different trade-offs:

1. Sort-then-scan: sort the list, then make a single pass — consecutive duplicates are adjacent, so each line just needs to be compared with the previous one.

2. Hash-set membership: process lines in order; for each line, check whether it's already in a hash set — if yes, it's a duplicate; if no, add it to the set and keep it.

3. Hash-count (for finding which values are duplicates, not just removing them): process all lines into a hash map counting occurrences, then filter to those appearing more than once.

Sort-then-scan: preserves sorted order, not original order

Time complexity: O(n log n) — the sort dominates; the scan is O(n). Memory: O(1) extra (if sorting in-place) — the sort can be done without a copy proportional to the input.

What you get: unique values, in sorted order — not their original order of first appearance.

When this is the right choice:

• You want the output sorted anyway
• Memory is constrained — you can't afford to hold a hash set proportional to the number of unique values
• You're processing data that's already sorted (then the sort step is free, and you get O(n) total)

When it's wrong:

• You need to preserve the original order of first appearance — sorting destroys that

Hash-set approach: preserves first-appearance order, costs memory

Time complexity: O(n) — each line is hashed and looked up once. Memory: O(u) where u is the number of unique values — you're storing a set of all unique strings seen so far.

What you get: unique values, in the order they first appeared in the original input.

When this is the right choice:

• You need to preserve original order
• The number of unique values fits in memory
• You're processing a stream and can't sort before seeing all the data

When it's wrong:

• Memory is severely constrained and the unique-value set is large — you're holding a hash set proportional to the input's diversity, which can be significant for large, high-diversity inputs

The "which duplicate to keep" question

"Remove duplicates" always implies a choice: when a value appears multiple times, which occurrence survives?

• First occurrence (keep the first time it appears, remove later occurrences): hash-set approach naturally does this — a value enters the set on first encounter, and later encounters are skipped
• Last occurrence (keep the last time it appears): requires either reversing the logic of the hash-set approach, or processing in reverse and then reversing the output
• Arbitrary occurrence (doesn't matter which): sort-then-scan naturally implements this — the "survivor" is whichever copy happens to be adjacent to the boundary in the sorted output

Most text-deduplication tools default to "keep first occurrence" — which matches the most intuitive expectation ("the original entry is the one that counts, and I'm removing re-entries"). But for cases like "this list was updated multiple times and the latest entry for each key is the correct one" — "keep last occurrence" is what you actually want.

Blank lines: are they "duplicates"?

An often-overlooked edge case in line deduplication: blank lines. If a document has multiple blank lines, are they duplicates — should all but one be removed? Or should blank lines be treated differently from content lines?

Three common behaviors:

1. Treat blank lines as duplicates — all blank lines are "the same," so only one survives (or zero, if you're removing all duplicates regardless of whether they appear more than once)
2. Ignore blank lines — blank lines pass through unchanged, regardless of how many there are; deduplication applies only to non-blank lines
3. Preserve blank-line structure — consecutive blank lines are collapsed to a single blank line; a pattern more like "normalize whitespace" than "deduplicate"

Most plain-text deduplication tools default to option 1 (blank lines are lines like any other — if they appear twice, one is removed). Option 2 or 3 requires explicit configuration or pre-processing.

Case sensitivity: a hidden assumption in most tools

"Line A and line B are duplicates" requires a definition of equality. For most tools, this means byte-for-byte exact equality — Apple and apple are different lines. Case-insensitive deduplication requires an additional step: normalizing case (usually lowercasing) before the equality check, while typically preserving the original case in the output (keeping whichever occurrence's case you decide to preserve).

For English text lists, case-insensitive deduplication is often more appropriate — a list of city names shouldn't treat London, london, and LONDON as three distinct entries. For code, log files, or data where case is semantically significant — case-sensitive deduplication is correct.

How to use the Remove Duplicate Lines tool on sadiqbd.com

1. Check the "preserve order" setting — most tools default to first-appearance order preservation (hash-set approach) — if your use case needs sorted output, many tools provide this as an option
2. Decide on blank-line handling before pasting your content — if blank lines exist and you want them preserved/collapsed rather than deduplicated, look for that option
3. For case-insensitive deduplication — check if the tool offers this; if not, pre-process by lowercasing, deduplicate, then consider whether original case matters in the output

Frequently Asked Questions

If I need to deduplicate a file that's too large to fit in memory, what's the approach? Sort-based deduplication is the classical answer — external sort algorithms can sort files larger than memory by sorting chunks and merging them — then scan the sorted result. The hash-set approach fails for inputs larger than memory (the hash set itself would exceed memory). For very large datasets, this is exactly the approach that command-line tools like Unix sort -u use — sort with external-sort algorithms to handle large files, then produce unique-sorted output. For most text-based use cases (the domain of a web tool like this), the entire input fits in browser/server memory, making this consideration academic — but it's the reason "sort-then-scan" remains a fundamental approach despite hash-sets being simpler in most code.

Is the Remove Duplicate Lines tool free? Yes — completely free, no sign-up required.

Try the Remove Duplicate Lines tool free at sadiqbd.com — deduplicate any list instantly, with options for sort order and case sensitivity.