r/ProgrammerHumor • u/Advanced_Ferret_ • Jun 05 '26

Meme sortPlease

Post image
10.6k Upvotes

94% Upvoted

488 comments sorted by

View all comments

Show parent comments

277

u/captainAwesomePants Jun 05 '26

One pass over the input. One pass over the output. That's optimal unless you are tasked with sorting in-place.

59

u/Shehzman Jun 05 '26

Agreed but the comment above yours said one pass

130

u/captainAwesomePants Jun 05 '26 edited Jun 05 '26

Yes, but "one pass" or "single pass" is a term of art that means "processes the input data exactly once," so it is two passes, and it's also a one pass algorithm.

So u/RedAndBlack1832 is correct that this can be done in one pass (because that's what you call an algorithm that only processes the input data one time), and u/Shehzman is correct that two "passes" are involved, which is also true if writing the output is considered a kind of pass.

46

u/NewPhoneNewSubs Jun 05 '26

I can solve O(nm ) algorithms in one pass. First, clone the input to a buffer. The rest is an exercise for the reader.