Introduction

When one item must appear before another, ordinary value sorting is the wrong tool. This is a dependency-ordering problem, which means the right model is a directed graph and the right algorithm is a topological sort.

Model the Data as Prerequisites

Suppose each task lists the tasks that must happen before it. In Perl, a hash of array references is a simple representation.

1use strict;
2use warnings;
3
4my %deps = (
5    generate => [],
6    compile  => ['generate'],
7    package  => ['compile'],
8    deploy   => ['package'],
9);

Here, compile depends on generate, and deploy depends on package. The graph is directed because dependency direction matters. If B depends on A, then A must appear earlier in the output.

This representation is easy to inspect, and it works well whether the items are tasks, modules, build steps, or records with parent-child requirements.

Use Kahn's Algorithm for Topological Sorting

A common iterative solution is Kahn's algorithm. Count how many prerequisites each node still has, start with nodes that have zero incoming dependencies, and keep removing them from the graph.

1use strict;
2use warnings;
3
4sub topo_sort {
5    my ($deps) = @_;
6
7    my %in_degree;
8    my %children;
9
10    for my $node (keys %$deps) {
11        $in_degree{$node} //= 0;
12
13        for my $parent (@{ $deps->{$node} }) {
14            push @{ $children{$parent} }, $node;
15            $in_degree{$node}++;
16            $in_degree{$parent} //= 0;
17        }
18    }
19
20    my @queue = grep { $in_degree{$_} == 0 } sort keys %in_degree;
21    my @result;
22
23    while (@queue) {
24        my $node = shift @queue;
25        push @result, $node;
26
27        for my $child (@{ $children{$node} // [] }) {
28            $in_degree{$child}--;
29            push @queue, $child if $in_degree{$child} == 0;
30        }
31    }
32
33    die "Cycle detected\n" if @result != scalar(keys %in_degree);
34    return @result;
35}
36
37my @ordered = topo_sort(\%deps);
38print join(" -> ", @ordered), "\n";

This produces a valid dependency order such as generate -> compile -> package -> deploy. The exact order among unrelated nodes may vary, and that is fine as long as every prerequisite appears before the items that depend on it.

Why a Custom sort Comparator Is Usually Wrong

Many first attempts try to solve this with Perl's sort, comparing two items at a time. That approach is fragile because dependency ordering is not a normal total order. A comparator must consistently answer which of any two values comes first, but dependency data often defines only a partial order.

For example, if A and B are unrelated, neither one truly depends on the other. A topological sort handles that naturally, while a comparator can become inconsistent and lead to undefined behavior.

Detect Cycles Instead of Guessing

A valid dependency order exists only if the graph is acyclic. If A depends on B, B depends on C, and C depends on A, no correct ordering is possible.

Kahn's algorithm detects this by checking whether it processed every node. If some nodes remain with nonzero in-degree, the input contains a cycle and the program should stop with a clear error instead of returning a partial result.

That error handling is not optional. Silent partial output is one of the worst failure modes for dependency resolution because it makes broken data look valid.

A Recursive Alternative

Depth-first search can also perform topological sorting. That version is often shorter, but it needs explicit state tracking to detect temporary visits and permanent visits. For many Perl scripts, Kahn's algorithm is easier to explain and debug because the queue and in-degree counts make the process visible.

If you are solving this in an interview or in maintenance-heavy production code, the iterative form is often the safer choice.

Common Pitfalls

Using normal sort for dependency ordering is the most common conceptual mistake. This problem is about graph traversal, not value comparison.

Forgetting to include nodes that have no dependencies at all can drop valid items from the result. Initialize every node, not just the ones that appear as children.

Ignoring cycle detection leads to partial or misleading output. Always fail clearly when the dependency graph is invalid.

Summary

• Ordering items by dependencies is a topological-sort problem.
• A hash of prerequisite arrays is a practical Perl representation.
• Kahn's algorithm is a clear iterative solution for producing a valid order.
• Cycle detection is essential because cyclic dependencies have no valid ordering.