sort and uniq in pipelines in Bash Scripting - Time & Space Complexity

Time Complexity: sort and uniq in pipelines

O(n log n)

Understanding Time Complexity

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

We want to know how the commands handle larger lists of data and how their work adds up.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

sort input.txt | uniq > output.txt
    

This code sorts the lines of input.txt and then removes duplicate lines, saving the result to output.txt.

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: The uniq command scans the sorted output once to remove duplicates.
• How many times: It reads through the sorted lines one by one.

How Execution Grows With Input

As the number of lines grows, sorting takes more time because it must compare and reorder many lines.

Input Size (n)	Approx. Operations
10	About 30 to 50 comparisons and rearrangements
100	About 700 to 1,000 comparisons and rearrangements
1000	About 10,000 to 15,000 comparisons and rearrangements

Pattern observation: The sorting work grows faster than the input size, roughly multiplying by more than ten when input grows ten times. The uniq step grows linearly, reading each line once.

Final Time Complexity

Time Complexity: O(n log n)

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

Common Mistake

[X] Wrong: "The uniq command alone removes duplicates from any list quickly without sorting first."

[OK] Correct: uniq only removes duplicates if they are next to each other. Without sorting first, duplicates scattered in the file won't be removed.

Interview Connect

Understanding how sorting and filtering commands scale helps you reason about data processing in real scripts. This skill shows you can think about efficiency when working with pipelines.

Self-Check

What if we replaced sort with a command that only partially sorts the data? How would the time complexity change?

Practice

1. What is the main purpose of using sort | uniq together in a bash pipeline?

easy

A. To get a sorted list with duplicates removed

B. To count the number of lines in a file

C. To sort lines but keep duplicates

D. To find the longest line in a file

Solution

1. Step 1: Understand what sort does

   The sort command arranges lines in alphabetical or numerical order.

2. Step 2: Understand what uniq does after sorting

   The uniq command removes duplicate adjacent lines, so sorting first groups duplicates together for removal.

3. Final Answer:

   To get a sorted list with duplicates removed -> Option A

4. Quick Check:

   sort + uniq = sorted unique lines [OK]

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

Common Mistakes:

• Using uniq before sort, which misses duplicates
• Thinking uniq counts lines instead of removing duplicates
• Assuming sort removes duplicates by itself

2. Which of the following is the correct syntax to remove duplicate lines from file.txt and sort the output?

easy

A. uniq file.txt | sort

B. sort file.txt | uniq

C. sort | uniq file.txt

D. uniq | sort file.txt

Solution

1. Step 1: Identify correct command order

   The file must be sorted first, so sort file.txt comes before uniq.

2. Step 2: Check syntax correctness

   sort file.txt | uniq correctly pipes sorted output to uniq for duplicate removal.

3. Final Answer:

   sort file.txt | uniq -> Option B

4. Quick Check:

   sort first, then uniq = correct syntax [OK]

Hint: Pipe sorted output into uniq: sort file | uniq [OK]

Common Mistakes:

• Placing uniq before sort, which fails to remove all duplicates
• Incorrect pipe placement causing syntax errors
• Trying to pass file as argument to uniq instead of sort

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
bob
carol
alice
bob

B. bob
alice
carol

C. bob
carol
alice

D. alice
bob
carol

Solution

1. Step 1: Sort the file contents

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

2. Step 2: Apply uniq to remove duplicates

   Uniq removes repeated adjacent lines, resulting in: alice, bob, carol.

3. Final Answer:

   alice\nbob\ncarol -> Option D

4. Quick Check:

   sort + uniq = unique sorted lines [OK]

Hint: Sort first to group duplicates, then uniq removes repeats [OK]

Common Mistakes:

• Not sorting first, so uniq misses duplicates
• Expecting original order instead of sorted
• Confusing uniq output with counting duplicates

4. You run uniq file.txt | sort to remove duplicates and sort lines, but duplicates remain. What is the likely problem?

medium

A. uniq only removes adjacent duplicates, so sorting after uniq misses duplicates

B. sort command is not working without options

C. file.txt is empty, so no output

D. uniq requires -c option to remove duplicates

Solution

1. Step 1: Understand uniq behavior

   Uniq removes only adjacent duplicate lines, so if duplicates are scattered, it won't remove them.

2. Step 2: Analyze command order effect

   Sorting after uniq means duplicates are not grouped before uniq runs, so duplicates remain.

3. Final Answer:

   uniq only removes adjacent duplicates, so sorting after uniq misses duplicates -> Option A

4. Quick Check:

   uniq needs sorted input to remove all duplicates [OK]

Hint: Sort before uniq to group duplicates for removal [OK]

Common Mistakes:

• Thinking uniq removes all duplicates regardless of order
• Believing sort alone removes duplicates
• Using uniq -c instead of uniq for removal

5. You have a log file access.log with many repeated IP addresses scattered randomly. You want a sorted list of unique IPs. Which command pipeline correctly achieves this?

hard

A. cat access.log | uniq | sort

B. uniq access.log | sort

C. sort -u access.log

D. uniq access.log | sort -u

Solution

1. Step 1: Understand sort -u option

   sort -u sorts and removes duplicates in one step efficiently.

2. Step 2: Why others fail

   Options A, B, and D all apply uniq before sorting, missing non-adjacent duplicates since IPs are scattered randomly.

3. Final Answer:

   sort -u access.log -> Option C

4. Quick Check:

   sort -u = sorted unique lines in one command [OK]

Hint: Use sort -u for sorted unique lines in one step [OK]

Common Mistakes:

• Using uniq before sort, missing duplicates
• Not knowing sort -u combines sorting and uniqueness
• Using unnecessary cat command