What is the difference between sorting and topological-sorting?

Question

What is the difference between sorting and topological-sorting?

Are they same or different thing?

Answer 1

At an abstract level they are connected: As Saeed and Stefan say, it's the difference between a total order and a partial order. That is a fantastically concise description, but sometimes not helpful when you're learning.

A total order means that, in the absence of repeats, when you sort something, you're going to get one unique proper answer. If you sort 3, 6, 2 in ascending order, you had better get one answer: 2, 3, 6.

A partial order is a little looser. The canonical example is the order in which you put your clothes on: You could put your shorts, then your pants, then your socks, then your shoes. That's a valid order. Or you could do shorts, socks, pants, shoes. But intuitively, you can't do shorts, pants, shoes, socks. It doesn't make sense to put the socks on after the shoes.

To formalize that dressing example, you usually show a dependency graph with actions ("put on shoes") as nodes, and directed arcs showing what node must precede what other nodes. A topological sort is an ordering of all nodes in a graph like that which respects the arcs. Meaning, if there's an arc from socks to shoes, then socks better be before shoes in the order.

So again, at an abstract level, they're connected. But they are absolutely NOT the same thing.