What are proven methods to sort/categorize a large number of parts? How would you recommend to sort your Lego parts? Finding a certain part in a box with parts of about 20 models takes ages.

Should I sort by color? Or by size? Another category?
I think the correct approach to this is to consider the whole process and not just the sorting part, although the short answer "sort by form" will still be valid.

The whole process is not limited to sorting, but in a more general way goes from the moment you decide to store a part away to the moment when you retrieve it to put it in a model.

As such, you have to keep in mind your ultimate goal: find the part you need for the model you're currently building. Most of the time, you'll have a specific part in a specific color in mind, and need to find it as fast as possible. But not always! Sometimes you don't care what color the part is in (invisible support structure), or maybe you can't see it (blind kids). In most cases, the form is at least as important as color, but sometimes it's just color you're after.

So what is sorting? Sorting is a way to do some of the finding work in advance so that when you need that particular part, you don't have to waste too much time. You'll also win serious time on the sorting since you do it for a lot of parts at the same time.

Let's assume you're after a specific part in a specific color, which will be most of the time. So that means your parts have to be sorted both by color and by form. That may prove too impractical for normal people, but keep in mind some serious builders do that.

So the trick is since you have two sorting criteria, you use one at the moment of building, and the other when storing or sorting parts (with discipline1, you'll sort when storing). Usually, you'll want to do as much tedious work when sorting, so you'll keep the color-sorting for when you're building. Color-sorting is the fastest, just think of a tub with all red bricks of all sorts and find 5 1x1 bricks in it, then picture the same task from a tub full of 1x1 bricks of all colors.

Again, this depends on what you'll end up doing with the bricks; if you want to build a lot of 2-studs-wide uniform walls for example, maybe a tub with one color of 2xn bricks makes more sense than separating the 2x2, 2x3 in different color tubs.

In any case, keep in mind the ideal way is to have each part in each color stored separately. If this is impractical, consider mixing parts which have as little in common as possible. If one container holds 1x3 and 1x4 bricks together, it will be more trouble to pick them apart than if you mix 1x1 and 2x3. Or, maybe you can mix 2L Technic axles with 1x2 slopes.

And the last thing to consider is how many of the part you have. If you have 2000 blue 1x1 bricks, and only a few dozens of other colors, don't mix them. Separate the blue ones and the others, or better, separate the blue ones but keep a few mixed with the others, so that the nearly-2000 blue-only 1x1 bricks can go to long-term storage. Similarly, make sure that rare parts for which you only have a few are easy to find, even if that means they have to have their own storage bin (maybe they can be mixed together, though).