sort and uniq in Linux CLI - Time & Space Complexity

Time Complexity: sort and uniq

O(n log n)

Understanding Time Complexity

When using sort and uniq commands together, it is important to understand how the time taken grows as the input size increases.

We want to know how the execution time changes when the input file gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

sort input.txt | uniq

This code sorts the lines of a file and then removes duplicate lines that are next to each other.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Sorting all lines in the input file.
• How many times: The sorting process compares and rearranges lines multiple times depending on input size.
• Secondary operation: uniq scans the sorted lines once to remove duplicates.
• How many times: One pass through all lines.

How Execution Grows With Input

As the number of lines grows, sorting takes more time because it compares many pairs of lines. Removing duplicates is faster since it just checks neighbors once.

Input Size (n)	Approx. Operations
10	About 30 to 50 comparisons for sorting, plus 10 checks for duplicates
100	About 700 to 1000 comparisons for sorting, plus 100 checks for duplicates
1000	About 10,000 to 15,000 comparisons for sorting, plus 1000 checks for duplicates

Pattern observation: Sorting grows faster than linearly, while duplicate removal grows linearly.

Final Time Complexity

Time Complexity: O(n log n)

This means the time to sort and remove duplicates grows a bit faster than just the number of lines, mainly because sorting takes more work as the file gets bigger.

Common Mistake

[X] Wrong: "The whole command runs in linear time because uniq just scans once."

[OK] Correct: Sorting is the main cost and it takes more than linear time, so the total time is dominated by sorting, not just scanning.

Interview Connect

Understanding how sorting affects performance helps you explain real-world scripts and commands clearly. This skill shows you can think about how tools behave as data grows.

Self-Check

"What if we used sort -u instead of sort | uniq? How would the time complexity change?"

Practice

1. What does the uniq command do when used alone on a text file?

easy

A. Deletes all empty lines

B. Removes repeated adjacent lines

C. Counts all lines in the file

D. Sorts all lines alphabetically

Solution

1. Step 1: Understand the uniq command behavior

   The uniq command filters out repeated lines only if they are next to each other.

2. Step 2: Compare with other options

   It does not sort lines or count all lines; it only removes adjacent duplicates.

3. Final Answer:

   Removes repeated adjacent lines -> Option B

4. Quick Check:

   uniq removes adjacent duplicates = D [OK]

Hint: uniq only removes duplicates if they are next to each other [OK]

Common Mistakes:

• Thinking uniq sorts lines
• Assuming uniq removes all duplicates anywhere
• Confusing uniq with wc (word count)

2. Which of the following is the correct syntax using a pipe to sort a file named data.txt and remove duplicate lines?

easy

A. sort data.txt | uniq

B. uniq data.txt | sort

C. sort -u data.txt

D. uniq -s data.txt

Solution

1. Step 1: Understand the order of commands

   To remove duplicates correctly, lines must be sorted first so duplicates become adjacent.

2. Step 2: Check each option

   sort data.txt | uniq sorts then pipes to uniq, which removes adjacent duplicates. uniq data.txt | sort runs uniq first, which won't remove all duplicates if unsorted. sort -u data.txt uses sort -u which is valid but not the pipe syntax asked. uniq -s data.txt is invalid syntax.

3. Final Answer:

   sort data.txt | uniq -> Option A

4. Quick Check:

   Sort before uniq to remove duplicates = A [OK]

Hint: Always sort before uniq to remove duplicates correctly [OK]

Common Mistakes:

• Running uniq before sort
• Using invalid uniq options
• Confusing sort -u with uniq

3. Given a file names.txt with contents:

bob
alice
bob
carol
alice
bob

What is the output of sort names.txt | uniq?

medium

A. alice
bob
carol

B. bob
alice
carol

C. alice
bob
bob
carol
alice
bob

D. bob
carol
alice

Solution

1. Step 1: Sort the file lines

   Sorting the lines alphabetically gives: alice, alice, bob, bob, bob, carol.

2. Step 2: Apply uniq to remove adjacent duplicates

   uniq removes repeated adjacent lines, so only one of each remains: alice, bob, carol.

3. Final Answer:

   alice bob carol -> Option A

4. Quick Check:

   Sort then uniq removes duplicates = alice, bob, carol [OK]

Hint: Sort first, then uniq removes duplicates in order [OK]

Common Mistakes:

• Not sorting before uniq
• Expecting uniq to remove all duplicates anywhere
• Confusing output order

4. You run sort data.txt | uniq but notice duplicates remain. What is the most likely cause?

medium

A. sort command does not work on text files

B. uniq command is misspelled

C. The file contains lines with trailing spaces or tabs

D. The file is empty

Solution

1. Step 1: Understand how sort and uniq treat whitespace

   sort and uniq treat lines with trailing spaces or tabs as different lines, so duplicates with extra spaces won't be adjacent identical.

2. Step 2: Check other options

   uniq misspelling would cause error, not duplicates remaining. sort works on text files. Empty file means no duplicates.

3. Final Answer:

   The file contains lines with trailing spaces or tabs -> Option C

4. Quick Check:

   Trailing spaces cause uniq to miss duplicates = C [OK]

Hint: Check for trailing spaces if duplicates remain after sort|uniq [OK]

Common Mistakes:

• Assuming uniq always removes duplicates regardless of spaces
• Ignoring trailing whitespace differences
• Thinking sort fails on text files

5. You want to count how many unique IP addresses appear in access.log. Which command correctly sorts, removes duplicates, and counts unique lines?

hard

A. sort access.log | uniq -c

B. uniq access.log | wc -l

C. uniq -c access.log | sort

D. sort -u access.log | wc -l

Solution

1. Step 1: Understand the goal

   You want the count of unique IP addresses, so you need to remove duplicates and count the unique lines.

2. Step 2: Analyze each option

   sort access.log | uniq -c counts occurrences but does not sum total unique lines. uniq -c access.log | sort counts duplicates before sorting, so misses some. sort -u access.log | wc -l uses sort -u to get unique lines, then counts lines with wc -l, which gives the unique count. uniq access.log | wc -l counts lines after uniq without sorting, so duplicates may remain.

3. Final Answer:

   sort -u access.log | wc -l -> Option D

4. Quick Check:

   sort -u then wc -l counts unique lines = B [OK]

Hint: Use sort -u then wc -l to count unique lines fast [OK]

Common Mistakes:

• Using uniq -c without sorting first
• Counting lines before removing duplicates
• Confusing uniq -c output with total unique count