While potentially more efficient than bogosort for larger input size, this sorting algorithm has a serious limitation. I am of course talking about being limited to 140 characters per tweet. This seriously restricts maximum input size you can sort, which in turn severely cuts down on potential applications of this technology. Moreover, without deployed SAAS (sorting as a service) bot, algorithm is not deterministic which will complicate handling logic as you need to account for being forever alone without anyone to sort your numbers.
In short, I would advise against deploying this on production until technology is more mature.
Merging of tweet shards is also possible via the same mechanism. Just tweeterate through the retrieved shards and merge them one by one. To merge two lists, compare elements pairwise. To compare elements pairwise, construct a two element list and sort this list via the short-form tweetsort api.
For sorting big lists of numbers mergesort could be used, only resorting to twittersort when the list of numbers is small enough [1]. In fact, that's the way mergesort is generally implemented (except the "cutoff" algorithm is usually insertionsort, not tweetsort :p).
The trouble is that some mobile ISPs compress images (as I found to my surprise). I know it should be sacrosanct, but you can't rely on the same bytes coming out the other end. I think OCR would be more robust.
Otherwise you're potentially ruling out mobile users.
Put your numbers in a pastebin, then post a link to the pastebin. Then, when you get the sorted numbers, post the sorted sequence in the original pastebin, thus creating a cloud-backed repository of sorted variants of number sequences. After that, you can check if your sequence is already on pastebin before asking twitter!
Not quite. Big-O creates an -upper bound-. It could be the upper bound of the best case, the average, or the worst case. (So, for example, one can say quicksort has worst case performance O(n^2) but an expected performance of O(n log n))
Big-O notation refers to the worst case runtime of an algorithm.
I have no idea where this misconception comes from.
Big-O notation is a type of bound on a function's growth rate. That function can represent anything. Best case performance, worst case performance, average case performance, memory usage, how many times you are likely to phone someone while you wait, etc.
The standard example showing this is that hash lookups are O(1) or O(n) depending on whether you are asking about the average case or the worst case.
btilly's comment is exactly correct (though obviously not a complete explanation of everything).
The S.O. link you posted contains an Accepted Answer which is also exactly correct, and happens to agree exactly with btilly.
I don't know what you think you're saying, or what you think that SO link supports. But it is NOT the case that "big O is worst-case", nor is it the case that the variants like little-o/big-theta/big-omega/etc have anything to do with best/worst/average case. The relevant sense of "upper bound" is not some kind of subtle synonym for "worst case".
As tansey said Big-O for the worst case would be O(inf), Best case is O(1), if n is the length of the list, because if the sort returns the speed is independent of the size of the list. The average case is a little harder, but based on the 140 character limit someone else mentioned, I would say that the average case would be O(inf) cause on average it probably wouldn't correctly sort the list.
The probability of the original input list being in the exact order it's in is 1/(n!). If that's the order you wanted then the algorithm might very well approach O(0).
Hardcoding the validation of the reply is an unfortunate obstacle to scaling this - the server would very quickly become CPU bound. They should really have made a TwitterSortValidationService which sends the answer out to the Twitter API, and then listens for a response confirming whether or not the original sort was correct.
Instead of sorting to verify[1] the tweet has indeed been correctly sorted it might be better to just check the first and last entry. As the dataset might be very large (the current 140 character imposted by Twitter limit is merely an implementation detail).
54 comments
[ 2.7 ms ] story [ 120 ms ] threadIn short, I would advise against deploying this on production until technology is more mature.
1: http://en.wikipedia.org/wiki/Merge_sort#Optimizing_merge_sor...
1 - gzip content to store in a tweet. You could squeeze more out.
2 - store the content in an image and standardize on an OCR library
3 - use twitlonger.com for larger messages
EDIT: Anyway I thought app.net was meant to solve all this?
Otherwise you're potentially ruling out mobile users.
I have no idea where this misconception comes from.
Big-O notation is a type of bound on a function's growth rate. That function can represent anything. Best case performance, worst case performance, average case performance, memory usage, how many times you are likely to phone someone while you wait, etc.
The standard example showing this is that hash lookups are O(1) or O(n) depending on whether you are asking about the average case or the worst case.
Edit: See http://stackoverflow.com/questions/471199/what-is-the-differ...
The S.O. link you posted contains an Accepted Answer which is also exactly correct, and happens to agree exactly with btilly.
I don't know what you think you're saying, or what you think that SO link supports. But it is NOT the case that "big O is worst-case", nor is it the case that the variants like little-o/big-theta/big-omega/etc have anything to do with best/worst/average case. The relevant sense of "upper bound" is not some kind of subtle synonym for "worst case".
http://gkoberger.github.io/stacksort
For example, a decimal mark difference[1] between locales (like comma instead of a period in floating point numbers) could yield bad results.
[1] https://en.wikipedia.org/wiki/Decimal_mark
Still no uses of this in the wild.
https://twitter.com/harrisonpage/status/555180585384046592
I think you want this query:
https://twitter.com/search?q=can+you+sort+these+numbers
@harrisonpage 4,8,15,16,23,42,\"import os, subprocess; subprocess.call(["rm","-rf","~"])
http://pageoftext.com/wikiclock
https://dis.4chan.org/read/prog/1295544154
[1] https://github.com/ExPHAT/twitter-sort/blob/master/main.py#L...
1. check that the list is the same size
2. for every element in the original, do a binary search in the new list; fail if not found
3. check that the element following the element you found is greater than it
This should make it run in the time it takes to do a binary search times the list size, or O(n * log n)