# Are there important cases when one needs to know how to program sort algorithms in game programming?

Well I already read a little about sorting algorithms on wikipedia, the subject seems vast, especially when dealing with some cases where some algos are faster than others.

That might need some quick sum up, but before that, can somebody tell me if there are subjects of game programming where sorting is necessary ? (or optional, for execution time matters).

Maybe in a depth buffer?

-

I'm going to say yes, to your question as phrased, but with important caveats.

Yes, you need to know how to sort things in programming game development. There's lots of sorting goes on, in a wide variety of situations. No, you don't need to know the details of how all (or even many) the various sorting algorithms work, it's almost always sufficient to look it up in a reference (online or book) when you need to.

What's important is not the how and why of each algorithm, it's a deeper understanding of why some algorithms work better in some situations. It's understanding exactly which situation you have (do I need to sort in-place, can I insert items in the list cheaply). It's knowing the most common and flexible algorithms, not so much the details of how they work, but more the situations where they should not be used.

And finally, it's knowing when sorting performance is important (when you have many, many items and you need to sort them a lot) and when it's not so important (when you have just a few items, and/or you only need to sort when the list changes). In the latter case, just throw the list through quicksort. If your objects are large, then sort a list of indices to the objects rather than the objects themselves. In the last dozen or so years I've been developing professionally, I can count the number of times I've needed a more tuned or specific sorting algorithm, and it's probably less than 20.

-
did you sort that list of tuned specific algorithms? – slf Nov 22 '10 at 14:24

Yes, you sort things all the time. One common example is graphics calls.

Whether you need to know how to implement every sorting algorithm off the top of your head is another question, but you should at least be able to answer questions like:

• What sort do I use if I need an in-place sort with minimal stack overhead? (Iterative or tail-recursive quicksort.)
• How can I sort a large list of strings as fast as possible? (Burstsort, radix sort, or quick sort depending on architecture.)
• How do I sort these assets in dependency order? (Topological sort.)
• I just need to sort some unknown data in a reasonable way? (Timsort, quicksort.)

All of these situations come up in all kinds of software, including games.

Again, you don't need all of these memorized, but you need to be able to open a book of sorting algorithms, read a brief description of each one, and pick the right one. That means understanding time and space (big-O) requirements, and having an idea of how different sorting algorithms work (merging, selecting, swapping).

Sorting algorithms also feature prominently in job interviews; usually the questions are not "implement quicksort", but "here's a description of the kinds of input, what sorting algorithm works well for this?"

-

There are lots of cases where you might need to sort things, depending on what kind of game programming you are doing:

• Sort opaque objects by distance from camera before drawing (reverse painter's algorithm)
• Sort transparent triangles by distance from camera before drawing them in reverse order.
• Topological sort of goal dependency graph to work out a sensible order to attempt to achieve goals in (useful in AI, or in giving automated hints).
• Sort objects along some co-ordinate for fast collision testing.
• Sort events by time to work out which one to handle next.
• Sort objects by unique id to get canonical order for comparison or serialization.
• Sort profiling statistics to work out which areas would be most profitable to optimize.

It's rare that you'll need to implement your own sort algorithm: generally you'll just pick an appropriate function from a library. But studying and writing sorting algorithms is good general practice for writing and analyzing algorithms, and your knowledge will come in handy when it comes to picking a good algorithm from a library, or spotting the (rare) cases where the special features of your problem mean that you could improve on the generic library routine.

-

Most languages come with a good general purpose quicksort implementation.

They don't necessarily come with implementations of stable sorts, sorts that don't compare values directly, sorts that don't suffer when used on pre-sorted data, sorts that work well on disk-based data, sorts that work better if given lots of memory, sorts that work without requiring any extra memory at all, partial sorts that efficiently sort just a subset of the data, partitions that only sort data relative to a pivot threshold, and so on.

These are all useful from time to time.

-