Ineffective Sorts

[MM_Dandy]

XKCD for 13 March:



This is funny enough, but when I read it, I immediately thought "And then there's me - I'm an ineffective sort."

[Мастер]

What language are these written in?

The first one looks very ineffective, if I'm analysing it correctly, it looks like it will never sort anything, and go into an infinite recursion if the length of the list is more than one.

ETA - that's if I'm understanding the syntax of the lines which assign values to A and B correctly. Under a different possible interpretation (again, I don't know what language this is), it looks like it returns the original list.

[Lance]

Yeah, I think it returns the original list and apologizes.

[Мастер]

OK, then in whatever language this is, one of the assignments to A or B must include the pivot, and the other must not.

Some of the others look like they will work sometimes :P

[MM_Dandy]

I think it's python, more or less. The bottom left is pseudo code.

Assuming that it's python, and that I've read the documentation for slices correctly, the assignment to A does not get the pivot, while the assignment to B does. So, the first time through, given a list of length 35, we have:

Code: Select all

// Passing in a list containing elements 0 - 16 of LIST (LEN == 17)
A = HALFHEARTEDMERGESORT(LIST[:17])
// Elements 17-34 of LIST (LEN == 18)
B = HALFHEARTEDMERGESORT(LIST[17:])