Sorting LEGO Faster

As I was sorting my ‘dump bin’, I began to wonder if there was a quicker way. Like most of you, having your LEGO sorted is nice, if not necessary, but every minute you spend sorting is not spent building. While there are many articles focused on how to organize your LEGO, there are very few spent on performing the sort itself.

In this post, a method to sort faster is presented. An overview of the problem as well as some Background information is covered first. Followed by some sorting algorithm Theory (feel free to skip this part) and lastly a method on How to Sort Faster is presented.

Contents

Background

Sorting LEGO can be a pain and often feels like a waste of time, until it comes time to build, then all that work pays off. Ideally, there would be a sorting machine you could get for your home, but for now, by hand is the best way, though tiered sorters can help.

Before starting this article, I looked around the internet for people covering this exact problem. Tom Alphin’s post gives a nice overview of the problem and a general approach to performing a sort. I was not able to find any other detailed discussion on this problem specific to LEGO. Please let me know if I’ve missed anything.

I will refer to ‘bins’ as the place where sorted LEGO pieces live, though they could be drawers or bags; the container type is unimportant. The number of bins and organization scheme has little impact on the time it takes to sort.

A few methods to perform a sort are covered below. The general trade offs are time and space. We will see later there is a better method than all of these in both time and space.

Single Pass

One way to sort would be to pick up a single piece from the pile and put it in its final location immediately, then repeat for each part until the pile is gone. The good news is that you waste no time digging or searching for a part. You also do not need any extra space to do this. The bad news is that it generally takes a while to find a bin, open it up, drop the part and return the bin.

This method works OK if you store your LEGOs in a chest of drawers where each drawer is in arms reach during the sort process.

Bin-by-Bin

Another way to sort is to find all the pieces that go into a single bin before moving on to another bin. This, of course, minimizes the time you spend shuffling bins around. It also does not require any additional space. The bad news is you spend a great amount of time digging through the pile to find pieces for each bin (and you will always miss some).

This method works best if your bins are very general, such as if you sort exclusively by color.

Two Pass

One improvement you can make is to make two passes through your pile of unsorted bricks, as outlined by Tom. This is a compromise between a single pass sort and the Bin-by-Bin sort method. The “bin management” time of the Single Pass method is minimized while the digging/searching time of the Bin-by-Bin method is also kept low. The downside of this method is it requires many square feet of space to store the pieces between the first and second pass.

Theory

While there is not much discussion on how to sort LEGO the quickest, there is a plethora of research on how to sort generic elements.

When it comes to sorting, two things slow you down:

1. How long it takes to move an element
2. How many times an element must be observed

Reasonable sorting algorithms fall into three complexity classes, from fastest to slowest:

1. Linear: O(n)
2. Logarithmic: O(n•log(n))
3. Quadratic: O(n²)

For general purpose sorting, a logarithmic method is the best you can do, but if there are a limited number of bins for the elements, sorting can be done in linear time.

At first, Counting Sort (a linear) sort sounds like it applies. You have a limited number of LEGO bins and at most you would observe and move each part once. But as discussed above, the time it takes to place a piece into a bin generally outweighs the complexity advantage.

Bucket Sort closely resembles the Two Pass algorithm, but requires more space. The second pass also devolves into either the One Pass or Bin-by-Bin sort.

The Bin-by-Bin sort reminds me of Bubble Sort, it is very easy to understand and perform, it just takes too long: O(n²).

It seems clear that a logarithmic sorting algorithm is needed. Quicksort applies quite nicely. To get a LEGO related overview, watch this German video.

Quicksort minimizes the time it takes to move an element as we will just be moving pieces from one pile to the next while also limiting the space needed to sort - especially since partitioned piles can be moved into ‘sealed’ bins and be stored out-of-the-way. The number of times an element must be observed is also limited (to log(n)).

A discussion about sorting would not be complete without mentioning my favorite sorting algorithm, Gnome Sort. Sadly, I cannot find a way to relate Gnome Sort to LEGO sorting, so we will just have to settle for this MOC I created:

How to Sort Faster

Use the divide-and-conquer steps below to sort your pile of organized LEGO quickly.

Steps

1. Partition (roughly) in half by category
2. Put half aside
3. Repeat on other half
4. Stop when you get a pile belonging to a single bin, repeat on put-aside piles

If you’d prefer, check out this video by Brick Scavenger, it explains the same process.

Explanation

Partitioning is where all the work is done. For each round of partitioning, your goal is to roughly divide the pieces into two equal sized piles where all the pieces for a given sorted bins are in one pile or the other. Categories will be different for each round - see the Example below for ideas.

Put one half aside, you will not need it till you are done with the other half. This is one of the best parts of this method: the unsorted pile is ignored and out of the way until the rest is put away.

With the half in front of you, pick another category and partition these pieces. Again, put one half aside and repeat.

Eventually you will be left with a pile where every piece goes into a bin. Put those pieces away, get out one of the ‘put aside’ piles and repeat. Do not worry too much about getting the halves equal, one third or one fourth still gives you a quick sort.

Optimizations

It often pays to remove the big pieces first as they slow everything down.

If you have a bit more space, you can speed things up a bit by partitioning the parts into more than two categories at a time. This especially applies when you get to small enough piles, you can afford to partition everything out into their final-bin categories. You should do this whenever you get down to having enough table space.

Example

I will use Michael Gale’s categories for this example. For illustrative purposes, I will only use red LEGO.

The goal is to sort a pile of LEGO into these six categories.

For the first category, I will sort all plates into one pile and the rest into another.

I will put ‘the rest’ aside and partition the big plates and tiles next, since they would get in the way.

Now I will put the big plates into a their final bin and partition the other plates and tiles.

At this point, I will put these two piles into their own bins. If your sorting scheme requires you to split plates and tiles, you would not stop with these piles, but continue partitioning. It is now time to bring out non-plate half I put aside earlier.

Since the remaining half is somewhat small, I will partition them into three piles, the way they are stored in their bins.

Evidence

Ideally I would take a pile of LEGO and repeatedly sort it in each method listed in this post and give times to illustrate the proposed method of sorting is fastest. I have not done this, but would welcome anyone to try this and report back.

Using back-of-the-envelope calculations, we can see how much faster it would be to sort 1,000 pieces into 100 bins. Let us say it takes 20 seconds to scoop a pile of parts into a bin. The fastest we could perform a sort would be 20 seconds * 100 bins = 2,000 seconds or 30 minutes.

For the Single Pass method, it would take 20 seconds • 1,000 pieces = 20,000 seconds or 5.5 hours.

For the Bin-by-Bin method, assuming it takes 10 seconds to find a piece for a given bin, it would take 10 seconds • 1,000 pieces + 30 minutes = 11,800 seconds or 3.3 hours

For the Two Pass method, let us say we can create 10 groups in the first pass. Assume it takes 1 second to group a piece, the first round would take 1,000 seconds. Using the Bin-by-Bin method for the second pass, we will say we can find pieces for a bin faster then the 10 seconds we assumed earlier (because of smaller, most concentrated piles) - say 5 seconds / piece. The second pass would take 5 seconds / piece • 1,000 pieces = 5000 seconds. The total time would take 1,000 seconds + 5,000 seconds + 30 minutes = 7800 seconds or 2.2 hours and a large table.

Using the suggested partition method above, each piece is partitioned log₂(100) = 6 times. Assuming you could partition 2 pieces/second it would take 6 • 0.5 seconds / piece • 1,000 pieces + 30 minutes = 4,800 seconds or just 1.3 hours and 5 extra bins.

We can see that the partition method is faster than the other methods and does not use much extra space.

LEGO, LEGOLAND, DACTA, DUPLO, PRIMO, FABULAND, SCALA, TECHNIC, MINDSTORMS, and ZNAP, etc. are trademarks or registered trademarks of The LEGO Group, which does not sponsor, authorize, or endorse this site.