Another possible way to do this is present the Turker with two vertical pieces already placed together. Ask them a yes/no question: do these two images match?
Iterate intelligently over your favorite sorting algorithm until you've placed all the images!
Note: requires more Turkers but each answer could be worth much less, maybe around $0.01
The lower the cost of the HIT (and the easier the question) the more you want to make sure you're screening for bots.
Make sure you have a gold standard question. For every HIT ask two questions; ask the legitimate question that you need answered and then on top of that, ask a simple "gold-standard" question that will determine whether the answer submitted is a bot or not.
For the gold standard, I like to choose two numbers, and store the sum of their values. Along with your HIT question, be sure to ask the Turker the value of their sum.
E.g. For a survey you ask the Turker "What is your favorite color?" But then along with that, you ask them "What is four plus fve?"
Be sure to misspell one value (e.g. remove a letter, etc). If the Turker doesn't respond correctly to the "gold standard" question, programmatically reject their response.
But then I think you are giving up the main advantage of using mechanical turk over just roughly matching pixels. It is possible matching pixels will get the wrong answer where a human, with the context of being human, will know what the image is supposed to be and get the write answer, captcha style.
Example: an iron fence with a scenic view behind and where the slices are too small for someone to match only two.
What about doing the same thing, but fuzzing a few pixels from each edge to avoid pixel distance matching? You could even make the edges just plain black for a few pixels from each edge. The human eye would be able to complete the image (it would just look like it has black bars), but I'm guessing it would be enough to prevent a simple algorithmic solution.
Edit: This is essentially the same idea as the iron fence posted above.
You can't use merge sort or any other standard sorting algorithm in this case. All these algorithms assume you can compare any two elements. To use a sorting algorithm, you would need to be able to say for any two images which is further left.
Iterate intelligently over your favorite sorting algorithm until you've placed all the images!
Note: requires more Turkers but each answer could be worth much less, maybe around $0.01