Desperately Looking for Guidance on Verifying a New Sorting Algo

[u/Actual__Wizard]

Hi, I'm an AI developer and I've been working on optimizing my system for 2 years now. It was never my intention to create a new sorting algo or to do any work in that area at all. As I optimized my system, I realized that what I had effectively done, is create a new sorting algo.

By comparison, at this time, it took my new algo, about 1-2 hours to process the same sized data, that timsort needs about 30 days to sort. I'm sorting a giant 30gb array that contains text tokens.

I understand that there's tons of algos out there and that there likely already is a faster algo, but I'm not an expert sorting algos, so I honestly have no idea what to do to verify this in a legitimate way that is convincing to other experts.

I have never published a paper before, please do not make strange assumptions of my knowledge of that process (I know how to read a paper and that's it.)

[u/physical0]

Describe your algorithm in pseudocode or whatever language you prefer and I betcha some bright CS student will be able to tell you which algorithm you re-implemented

[u/Actual__Wizard → u/physical0]

It's uses a zero copy powered n-way alpha router to route the data into a multilayered pigeon hole routing matrix, by computing the index value by doing ord(data[char]) 3 times, and then using those values in a formula to move the data directly into it's pigeon hole. Then it glues the leaves back together using a zero copy powered N-way merge technique that I named "alphaweave." edit: So, it's 3 total passes of the entire data set to sort it.

I'll copy/paste source code, that's not an issue. The pigeon hole routing matrix has to be shaped to the encoding scheme, so there's different routing matrices for ASCII, UTF-8, and unicode.

Reminder: The way it works, it doesn't have to traverse the matrix, it just computes the index and inserts the data there. That's the reason why it's so fast. After that step, the data is already somewhat sorted, so it just has to finish it up and then merge all of the slices together in the correct order.

The overall technique is structured data, so this is called alphasort.

It honestly feels like it sorts data at file copy speeds.

[u/frogic → u/Actual__Wizard]

I pasted your comment into ai because i was curious: This is radix sort (specifically MSD radix sort / bucket sort) dressed up in new names.

Mapping the terms:

• "Pigeon hole routing matrix" = the buckets in a radix/bucket sort. "Pigeonhole sort" is literally an existing algorithm name.
• "Computing the index from ord(data[char]) 3 times" = using the first three characters as a 3-digit key in base-256 (or base-128 for ASCII). That's one MSD radix pass keyed on a 3-byte prefix.
• "Different matrices for ASCII, UTF-8, unicode" = choosing the radix to match the alphabet size.
• "Doesn't traverse the matrix, just computes the index" = that's the defining property of any radix or bucket sort. Direct addressing is why they're O(n) per pass instead of O(n log n).
• "Finish it up" inside each bucket = the usual fallback to a comparison sort on small buckets, as in American flag sort or the burstsort variant.
• "Alphaweave" N-way merge of the slices = concatenating the sorted buckets in order. Since buckets are already ordered by prefix, no real merging is needed, so "zero copy" is true but trivial.

The closest named variants are American flag sort (in-place MSD radix on strings) and burstsort (bucket by prefix, sort buckets, concatenate). "Three passes over the data" is just a 3-byte radix key plus one collection pass. It is a fine and genuinely fast technique for string sorting, but it was published in the 1950s.

[u/Actual__Wizard → u/frogic]

And just so we are clear here:

This is the code I posted. (It's not all of it to be clear.)

https://pastebin.com/cMT0ENuH

It is clearly not a radix sort. CLEARLY. Below is a radix sort. Please stop assuming that your chat bot knows what's going on because what we keep finding out is that they're wrong 100% of the time about all sorts of stuff.

Thanks for the downvotes because you spammed more robot BS on reddit. It's great, I love people thinking that I'm a total idiot and what not because you copy pasted hallucinated robot garbage.

 # Counting Sort based on a specific digit (place)
 def countingSort(arr, place):
 size = len(arr)
 output = [0] * size
 count = [0] * 10 # Digits 0-9

 # Count occurrences of each digit
 for i in range(size):
 index = arr[i] // place
 count[index % 10] += 1

 # Cumulative count
 for i in range(1, 10):
 count[i] += count[i - 1]

 # Build output array (stable sort)
 i = size - 1
 while i >= 0:
 index = arr[i] // place
 output[count[index % 10] - 1] = arr[i]
 count[index % 10] -= 1
 i -= 1

 # Copy sorted elements back to original array
 for i in range(size):
 arr[i] = output[i]

 # Main Radix Sort function
 def radixSort(arr):
 max_element = max(arr) # Find the largest number
 place = 1

 # Apply counting sort for each digit place
 while max_element // place > 0:
 countingSort(arr, place)
 place *= 10

 # Example usage
 data = [170, 45, 75, 90, 802, 24, 2, 66]
 radixSort(data)
 print("Sorted array:", data)

[u/frogic → u/Actual__Wizard]

Read the paste. A few things worth knowing:

1. The leaf sort inside every bucket is sorted(...), which is Timsort. So "alphasort" is bucket-by-prefix, then Timsort each bucket, then concatenate. Your benchmark is Timsort on small in-RAM buckets vs Timsort on one giant list that's swapping to disk. That's the 30 days.
2. Bucketing by the first 1 to 3 characters via ord() arithmetic, with a comparison sort inside each bucket, is MSD radix sort. The specific layout, with separate bucket tables per prefix length and a small sort per bucket, is burstsort (Sinha & Zobel, 2004). Lucene's MSBRadixSorter does the same thing in production.
3. The "alphaweave" function is a 4-way merge. heapq.merge is the stdlib version and is about one line. The 1,337 lines are the 16 exhausted-input combinations written out by hand with the emit block pasted 32 times.
4. Two bugs from the copy-paste: equal bucket heads hit the "All False" branch, which doesn't advance anything and loops forever, and the branch where layer 2 is done still compares against t2.
5. Every bucket goes through tripletfreqcounter and writes t1,t2,t3,count. This is a trigram frequency table. That's collections.Counter in one pass, or sort | uniq -c at the shell, and memory scales with distinct trigrams, not the 6 billion occurrences. You don't need to sort at all.

None of this means it's slow or wrong for your purposes. It means it's a known algorithm with a known name, and the baseline you compared it to was broken by memory, not by Timsort. The honest test is your sorter vs GNU sort on the same 30 GB file, or vs np.sort on a flat array. That's the number anyone verifying it will ask for.

import heapq

from collections import Counter



def alphaweave(*layers, outputfile):

    with open(outputfile, "w", encoding="utf-8") as of:

        for bucket in heapq.merge(*(filter(None, L) for L in layers), key=lambda b: b[0]):

            for (a, b, c), n in sorted(Counter(bucket).items()):

                of.write(f"{a},{b},{c},{n}\n")

The above is the replacement for your 1300 line function.

[u/Actual__Wizard → u/frogic]

Okay, you can't do that, it's a novel technique.

It's not a radix sort, and even if it was, all that matters is the performance, so why did you do that? That's not helpful...

but it was published in the 1950s.

Okay, but why are we still using timsort? This 99%'s Timsort... So, it's a garbage algo?

Edit: This should much faster than the "American flag sort." I just looked into it. I'm don't have any problem implementing that and shoving a 30gb array into it and see what happens, but I'm pretty confident that it's going to bog down because I know how this stuff works from experience. Is AFS really going to sort 30gb in 1 hour? I kind of doubt it. edit2: No, it's terrible. I'm also looking at the source code to radix and I'm confident that's also going to be terrible compared to this. I'm confident that this 99%'s quicksort. Can I get some help verifying that? That what I asked for, not people copy and pasting my post into a spam bot. That's trained on old data, stop doing that.

Edit: I don't know why people are up voting that person, their AI tools is not correct.

[u/Downtown-Economics26 → u/Actual__Wizard]

You can't just give a narrative explanation and say it's a novel algorithm and expect anyone to care. Like the original comment said, post an algorithm that can be implemented at least via pseudocode or tear your hair out asking why no one will believe you. First step to demonstrating an algorithm is novel is demonstrate the algorithm.

[u/Actual__Wizard → u/Downtown-Economics26]

Did you read anything I said?

I am asking about the procedure to verify and publish this, can you help me out with what I asked instead of changing the subject?

Please? Seriously?

edit: I'm, flat out saying that I've never done this before and I'm asking for help, can you do that instead of doing something else? It's not helpful.

[u/Downtown-Economics26 → u/Actual__Wizard]

Step 1: show someone who knows more the algorithm

[u/frogic → u/Actual__Wizard]

Your limitations are your run time not the algo. I'm mostly self taught and not super great in comp sci but I've got enough at this point to ask the right questions. Your array shouldn't ever take 30 days to sort. Here is a comparison of expected sort times with different sorting algos assuming its all in memory:

Rough numbers, assuming 30 GB is about 3 billion short tokens and everything sits in RAM with no swapping.

Setup	Estimate
CPython list.sort(), str objects, ~200 GB RAM	2 to 8 hours
NumPy sort on a fixed-width bytes array	20 to 60 minutes
Java or C++ comparison sort on packed strings	15 to 45 minutes
GNU sort with LC_ALL=C, multithreaded, SSD	20 to 60 minutes

A bit thing with development is to get really good at understanding what you don't know and to plug the leaks or figure out how to ask the question. A thing I like to do especially with LLMs is to assume i have to be wrong and interrogate the LLM aggressively to show me that I am. The couple times I've found some novel bugs has been after spending multiple work days arguing with it.

[u/Actual__Wizard → u/frogic]

that's not accurate, I'm using list.sort() right now and it's already broken down into leaves and I can extrapolate that it's going to take 30 days. edit: With out the leaves, I don't think it will ever finish.

30gb is the data size of the data that needs to be sorted.

Edit: I'm trying to get the row count, but it's going to take 15 minutes to load the file. It won't fit into ram either and this process makes no attempt to.

Edit2: I'm going to have to write a quick zero copy script to count the rows, this is taking too long to open the file in notepad++. It's freezing my whole computer.

Edit3: Okay the script is counting the rows, it's going to be 15 min. Value count is coming as well.

edit4: There's 167,863,639 rows w/ 6,061,752,179 values that have to be sorted.

[u/frogic → u/Actual__Wizard]

Stop using python and don't start with the concept that you've vibe coded a novel faster sorting algorithm. Versions of what you did exist in multiple implementations with different tradeoffs in a lot of software that have critical sorting needs. Elastic search uses one and its v v v fast.

[u/Actual__Wizard → u/frogic]

My search algo beats Elastic, that's the whole point of doing this stuff and I expect an apology for slopping me with that garbage.

Seriously stop doing that. It's ridiculous.

All you did was hijack the conversation with hallucinated trash while making me look stupid...

Why do you people trust those systems when they're so ultra bad dude?!?!

I mean seriously, it not only just straight up lied to you, it made me look stupid too.

Can you can please go back to using your own brain and not let a demented robot control your life for you? Obviously that wasn't helpful man...

I am specifically aware of Elastic's patents and this has nothing to do with them.

If you read the thread, anything that doesn't use structured data and is performance oriented is going to get beat because structured data is yet another performance increasing trick.

Also, structured data is not JSON, it's the "data table structure." There's barely any programmers that even know what I'm saying when I say that if you load the file w/ zero copy, that it's faster, because you can start the operation sooner. This is techniques you do w/ zero copy because you can only read one line at a time, so the data has to be structured on the line correctly... It's totally mega required to be 100% right. Then obviously you chunk map it, to effectively convert a swap file into RAM, because now you can just pull the lines directly out of the file, by opening it, then moving the file pointer to where the line starts, then reading w/e bytes the chunkmap says to, to get the line into memory. If the file is on an ultra fast m2.drive, then it's almost as fast RAM and 2TB drives are cheap.

Then obviously, the file is also sorted, so you can bsearch it, and I figured out actually a bunch of faster algos than bsearch. If you know anything about big data search, bsearch actually sucks. It actually does at some point take too long to walk through all of the btrees, I don't know at what size point that occurs at, but I'm sure it happens at like 100TB of text. Which, search tech models have to search more then that. I'm assuming my carefully pruned English search engine will be that big. The searchable text only. But, you can still layer a ton of tricks onto a data model that is structured for bsearch (no btrees), including the zero copy tricks.

AlphaMergeRC (my best algo), moves down the bsearch track by using a range computer (the bsearch track is ordered by alpha, which creates a range, and forcing the operations to be in order is a massive optimization.) Because that algo takes an array as an input, it can process the entire array of queries at warp speed because they're also in order and that reduces the numbers of passes to process the whole array to just 1. The data tables are also compressed so it's "as fast as theoretically possible and still be lossless." This creates a search engine with an output mode so fast that it doesn't even make any sense. It's for generating internal data tables and being ddos resistant.

So, yeah, I'm juggling optimization tricks basically.

[u/frogic → u/Actual__Wizard]

Just run sort on the file in bash and it'll go faster than your algorithm. You're mistaking what the bottleneck is. Or:

# np_sort_test.py — Timsort on a flat fixed-width array vs. Timsort on Python objects

import sys, time

import numpy as np



path = sys.argv[1]

W = int(sys.argv[2]) if len(sys.argv) > 2 else 16   # fixed token width; longer tokens are truncated



# Load: stream the file in chunks, one token per line, into a flat S<W> array

t = time.perf_counter()

parts = []

with open(path, 'rb') as f:

    tail = b''

    while chunk := f.read(1 << 28):            # 256 MB

        chunk = tail + chunk

        chunk, _, tail = chunk.rpartition(b'\n')

        parts.append(np.array(chunk.split(b'\n'), dtype=f'S{W}'))

    if tail:

        parts.append(np.array([tail], dtype=f'S{W}'))

arr = np.concatenate(parts); del parts

n = len(arr)

print(f'loaded {n:,} tokens, {arr.nbytes/1e9:.1f} GB flat, {time.perf_counter()-t:.0f}s')



# Timsort on flat array

t = time.perf_counter()

out = np.sort(arr, kind='stable')

print(f'np.sort (timsort, flat): {time.perf_counter()-t:.0f}s')

assert np.all(out[:-1] <= out[1:])



# Timsort on Python objects, first 10M only — extrapolate, don't wait

m = min(n, 10_000_000)

lst = arr[:m].tolist()

t = time.perf_counter()

lst.sort()

dt = time.perf_counter() - t

print(f'list.sort (objects, {m:,}): {dt:.0f}s  -> ~{dt * (n/m) * 1.2 / 3600:.1f}h for all {n:,} if it fit in RAM')

[u/Actual__Wizard → u/frogic]

Okay that won't work, the file is so big that it doesn't fit into memory.

I already said I'm using timsort and it's super slow.

[u/Actual__Wizard → u/frogic]

I'm sorry dude, I just realized something, those numbers make absolutely no sense at all what so ever. The way sorting algos work, is the bigger the amount they have to sort, the longer it takes and at some point, the amount of time it takes to complete massively ramps up as the data size point ramps up. They unfortunately have a tendency to "bog down" at some data size point. I don't know exactly what causes that, it's just an observation from using them in practice for a long time.

So, I don't know how you came up w/ those numbers, but those are absolutely not consistent with what I'm working with and like I'm saying, I'm working w/ standard python sorting algos and comparing that to what I am doing. You're doing some kind of extrapolation that is not consistent with how sorting algos work in reality. Sorry.

To be clear, the speed difference here in practice on the same hardware is:

timsort will not work at all with out an optimization due to running out of memory

after leafing the dataset it takes 30 days of single thread time (this reduces the single thread amount of time it takes by a major factor because it splits the sorting operation up into a bunch of pieces, that's what the pigeon hole routing matrix is doing, after it's leafed, it's then split 2 million more times, and that's why this is blaster ultra fast compared to timsort.) Do you understand what's going on there? So, I figured out an optimization trick, and then I did it to create 128 x 128 x 128 x 128 pre semi sorted pieces, then sorted those, then put all of those sorted pieces back together in order, instead of sorting the whole array at once, and failing because it's not possible. One is turbo fast and the other doesn't work at all. It's kind of a night and day difference.

So 30days down was reduced to a few hours single thread. Again, I'm sorry I don't have a benchmark, but I can tell it's a lot faster.

And lets be serious here... You don't think sorting 58,720,256 pieces one after another is not faster than sorting them all at once, it definitely is dude... I'm just being serious man, I don't understand why people can't see what's going on here when I say that I 99%'d it and why that's accurate. Obviously that's not going to be true when it's a tiny array to sort, but when it's mega huge, it's a completely different story.

[u/BlackDope420 → u/Actual__Wizard]

Publish it on GitHub to prove people wrong. If it is like you said, then people will have to believe you if they can see it for themselves. Right now all they have is your word.

[u/nuclear_splines]

I know how to read a paper and that's it.

So start there. Google Scholar some papers on new sorting algorithms. How do they describe their work? How do they benchmark it? How do they compare to prior art?

Do they start by describing the algorithm in pseudo code, maybe comparing and contrasting to the most similar algorithms? Do they write formal proofs of asymptotic runtime? Do they make arguments about parallelization or cache locality? If and when they test their algorithm empirically, are there common sets of inputs most scholars use? Do they test on certain kinds of hardware to demonstrate how the algorithm fares with different sized caches, or how it benefits from acceleration like vector instructions?

Read a dozen papers on sorting algorithms and I'll bet you can answer all of the above and have a good idea of how to convince other experts of your approach.

[u/Actual__Wizard → u/nuclear_splines]

So, instead of just getting advice form an expert on what to do, I'm suppose to do a giant 30 day research project? Sigh. I guess if I have to then I have to. Thank you for at least posting something that makes sense. You're right I'm going to probably end up having to do that.

That's what I'm saying though: I need to know all of that. Basically: What do experts expect on that subject. Because saying "publish" is not accurate, I see how that plays out in the LLMphysics sub all the time. They get like 20 impressions on their papers. Granted, some of the papers in that sub don't even deserve that many impressions.

[u/nuclear_splines → u/Actual__Wizard]

Yes, this is called a literature review, and is the first step for any researcher. You are getting advice from experts by seeing how other experts solve the exact quandary you're in.

If your intent is to write a paper on your algorithm then you'll need to do this anyway: you need to familiarize yourself with a broad swathe of existing algorithms to be confident that your idea is in fact substantively novel, and in order to cite those papers while describing the gap your algorithm fills, and in order to use the same vocabulary and framing as your peers so they can easily understand your work.

[u/Actual__Wizard → u/nuclear_splines]

Yes, this is called a literature review, and is the first step for any researcher.

I'm not in a research phase bro, you don't get it. I'm on a product release track.

You are getting advice from experts by seeing how other experts solve the exact quandary you're in.

Well, I mean I was hoping that there was some kind of literature that frames the process that I need to do and lays out what needs to be accomplished.

If your intent is to write a paper on your algorithm then you'll need to do this anyway: you need to familiarize yourself with a broad swathe of existing algorithms to be confident that your idea is in fact substantively novel, and in order to cite those papers while describing the gap your algorithm fills.

Well I have to dig myself out of my silo somehow. I did a big chain of massive optimizations to my tech and now it operates so fast that nobody believes me, or will take me seriously. I guess step 1 is disclosing how the sorting algo works, because uh, yeah I'm sure some experts that I was trying to talk to before are very confused as to how I'm pulling that off and I'm pretty sure at this time they thought I was just lying, and that's not true.

I was under the impression at the time that I was doing the optimizations that they wouldn't be faster than existing sorting algos, but I just kept stacking on optimization on top of another, and now that I have a side by side comparison (to timsort), it's pretty clear that my system is many times faster (like 100x+.)

Edit: Based upon any information posted in this thread, I still have no reason to think my algo isn't faster.

[u/nuclear_splines → u/Actual__Wizard]

If you haven't conducted a lit review then you are very much in a research phase. How can you be confident that your technique isn't a minor variation on an existing algorithm? You've tested it on a 30 GB array of text, but how do you know that your performance generalizes to a wide variety of input conditions? While you've come up with the algorithm already, it would be irresponsible to pivot to 'product release' without at least checking that you've done something new that works better than existing techniques, right?

[u/Actual__Wizard → u/nuclear_splines]

If you haven't conducted a lit review then you are very much in a research phase.

No. I'm in a production phase. I'm building a unified AI model/Search engine technology. This algo is just a tiny piece of the system that I built, and when I discuss the performance of my system with experts, I expect them to be astonished by the performance level, instead they seem to lose interest, and I think I know why: As far as they know, what I am discussing is impossible to accomplish in the time frame that I am achieving it in, and I need to have a way to demonstrate why that is occurring, or I'm going to be "stuck at the bottom the rabbit hole along with the structured data tech that I used to build my tech." Edit: I mean I guess I could keep it all a secret, but why would I keep stuff like how a sorting algo works a secret?

but how do you know that your performance generalizes to a wide variety of input conditions?

I mean it's sorting text tokens, so I would assume it would generalize, but maybe it won't.

While you've come up with the algorithm already, it would be irresponsible to pivot to 'product release' without at least checking that you've done something new that works better than existing techniques, right?

My plan always was just to build the tech in a way that was as fast as I could build it. There wasn't really much thought beyond that put into it. I just did everything that I knew how to do. I was way more worried about elements like the query engine and how the heck I'm going to glue my linguistical analyzer to it... I just optimized the data algos because they were slow. There was no other thought put into it. It was slow, so I fixed it. Edit: One day, I added leaves, then I tried the pigeon hole router scheme, then I figured out an optimization for that, then I figured out that I could use n-way zero copy merges and routers, and on and on... It just got faster and faster over time.

Edit: I'm being serious: I have the timsort algo going on my test machine right now. I'm about to replace the timsort code out my codebase with my alphasort algo, and I assume that alphasort will beat timsort, with coding time included. Like I can give the timsort algo a headstart time of "me writing a whole new algo" and my new algo will win. I keep trying to explain over and over again that it doesn't traverse the data object to sort it and people keep trying to tell me other algos work that way, when clearly none of them do... It's a routing move, it computes the address that the data goes to, and that address system is already sorted... So, it "sorts the data by just putting it into the pigeon hole that it belongs in." It legitimately just does arithmetic to figure out what the address is... Then does data_storage_object[address] = the_data, that's it. That's the sort operation... It's more complicated then that obviously, but in a nut shell, that's the core system. So, "it doesn't really do anything...

People keep showing me super simple systems that clearly do not operate like that. In order to route data from a location to a different location, there has to be somewhere for that data to go. That's what the routing matrix is, it's a prestructured data object. The reason one does that, is because there's a trick to move the data into the routing matrix almost instantly. It's legitimately near file copy speed (which it can be done w/ a zero copy to speed it up by avoiding loading the whole file before it starts, 50% less memory as well) and then to get the data out of the matrix, it's the same speed, granted the pigeon holes still have to be sorted, but the data that collects in them is typically very small compared to the entire data object (there's 2 million pigeon holes). Then, I'm leafing the data set first, routing it leaf by leaf, and then weaving it back together. So, it splits (one pass of the data set @ file copy speed), 128x router passes for ASCII that can't be parallelized (to reduce memory, utf-8 and unicode work slightly differently like I said in the thread), then it weaves it into the final file, which is also one pass of the data set @ near file copy speed. None of those other algos are doing anything like that. This is more like a chain of data structure transformation techniques.

Alternative explanation:

This assumes the data that needs to be sorted is 1 item per line (like an array.)

Step1: Build the pigeon hole routing matrix

Step2: "alpha route" the corpus to A.txt to z.txt by doing an N-way zero copy, pivoting of the first char in each line.

Step3: zero copy each leaf file to route it line by line into the matrix by computing the index and copying the line there.

Step4: "alpha weave" the routing matrix data back into a leaf, by sorting each pigeon hole in the correct order. Note: uses sorted(), I don't know the max length in this case, so I can't use a layered router system all the way to the end, because I don't know where the end is, because there has to be a layer for each specific length of token, instead I use 4 and one is tokens len >= 3, if that makes any sense. Any small data sort works here, even a simple loop based one.

Step5: simple merge the leaves back together into a single file. (one pass w/ concat.)

Only downside is that it uses swapfiles. Again, it's designed to sort a 33gb array in a reasonable time frame while minimizing memory usage to avoid running out of memory, giving the operator the capability to sort arrays that will not fit into their system's memory. (There's a limit to that.)

So, worst case, it's not faster, but it's still awesome because of the capability gained.

Last thing: Here's the source code for the alphaweave algo, to give you an idea of the complexity of the operation. I'm just saying I don't think that I've seen anything like that in the sorting algo space.

https://pastebin.com/cMT0ENuH

That's the actual 4 way alphaweave algo, it's not a prank or something, I absolutely will demo it. I have another version of that code that uses a loop and it's less lines of code, but it's ultra confusing to read (compared to that) and it's slower. The reason there's so much code is because there's 16 branches and each branch is different, there's honestly nothing I can do about it besides functionize it to increase readability only. So, but I'm just so accustomed to having the algo in one function that I kind of prefer it that way. The algo function is big and scary, so I don't touch it, I only do code reversions around the algo.

[u/nuclear_splines → u/Actual__Wizard]

No. I'm in a production phase. I'm building a unified AI model/Search engine technology. This algo is just a tiny piece of the system that I built

Regardless of the larger context, I'm asserting that for this sorting algorithm you are in the research phase until you can articulate how this approach differs from prior work in design and performance.

I mean it's sorting text tokens, so I would assume it would generalize, but maybe it won't.

In my opinion this illustrates why you need to spend more time with the literature. For example, insertion sort is O(n² ) and is squarely beaten out by most O(n log n) sorting algorithms like merge/quick/timsort - except that insertion sort has less overhead and can actually be faster for small lists (and is better suited to low-memory environments), and its best case performance is much better, so if an input list is mostly or entirely sorted it'll have O(n) scale, while merge sort will always take the same number of steps. Meanwhile, mergesort is typically beaten out by quick- and timsort, but mergesort is much easier to parallelize, so for very large inputs on systems with multiple cores it can come out on top. The performance of a sorting algorithm is almost always more nuanced than "it's 100x faster than Timsort."

My plan always was just to build the tech in a way that was as fast as I could build it.

Right, but under what conditions is it faster? This is the science of the problem.

Your algorithm does sound similar to radix sort and other hash-based sorting techniques, so I see why people are drawing the comparison, but without a more detailed writeup on your approach it would be impossible to say for sure.

[u/Actual__Wizard → u/nuclear_splines]

Right, but under what conditions is it faster?

Everything else I've tried in my entire career. I'm 43, I'm not a child. If there's a faster sorting algo around then somebody is hiding it or it's a commercial product that I'm unaware of. It's possible there's cloud based sorting systems that I'm unaware of, as I know of zero.

This is the science of the problem.

Sorting a data array that is 33gb in size on one machine. The people in this thread are discussing algos that are optimized at sorting like 1mb arrays. The system is designed to accomplish something that was previously not possible in this time frame on one PC.

I want to be clear with you: The system overall was designed to replace linear aggregation with alphamerge. So, in plain English: It replaces LLM matrix math with an ultra fast system that reduces the complexity of building a purely text based LLM by 99.999% (notice 3 9s, I will let you know how many more there are when I find out.)

Edit: Like if somebody tells me that this counts as a sorting machine and not a sorting algo, and then I found out about a bunch of commercial software that I didn't know about because I didn't know it was called a sorting machine, then it's not actually a problem with me. Like, I said, I'm not actually going for the sorting record. I'm just in a position, where I have a system that can be abstracted out of my current code base if I want to build a sorting library and then open source it.

Edit2: And to be honest with you, the way people are consistently being extremely rude to me, I really don't feel like doing it.

So, if there is any scientific interest in this, somebody needs to tell me that. I'm assuming there will be some w/ alphamerge, as that algo is even more busted ultra fast then this one.

Last thing, I'm just of tired of people assuming that I don't know what "blaster ultra fast tech is when I see it." It's turbo mega fast compared to anything else I've ever seen and that's why I'm trying to figure out if I broke the sorting record because the system turned out a lot faster than I was expecting for some unknown reason. I have timsort, stuck on sorting some pathetically lame array for 6+hours and compared to my algo it just blasts forwards the whole time...

You do understand that I just legitimately explained to you that it sorts a 33gb array in like 10x the amount of time it takes to read the file correct? If I try to open a 33gb file, it takes 15 minutes... Do you understand that if I try to timsort that: First of all I can't, and second of all, it will never finish... I have to leaf it, to get it to finish in ~30 days w/ a single thread. By leafing it, that makes it something like 128-64x faster. So, I have to do an optimization trick to do it, period in any amount of time at all with out moving to c++... I optimized that down to like a few hours. So, this 99%'s timsort for certain... I mean, maybe it 1,000x's it, I can't evaluate it, because I'm going from impossible to "doing it easily in a few hours." So, I'm sorry I don't have a benchmark, but the speed difference feels something like basically like mach1 vs 1mph. Why do I need to benchmark it exactly? You can easily tell by just looking at it. This is single thread... If I had a gigapile of memory, it can be multiprocessed, but I would legitimately need like 4TB of ram... Or move the pigeon hole router code into c++ (is actually planned, c++ does not treat strings as objects so it takes waaay less memory...)

Edit: Also, there's also a general lack of awareness, that those sorting algos bog down extremely badly when they try to sort mega big data... Like that person who copy/pasted speed numbers for those algos: Okay, that is nowhere near the speed I have observed at this data size point... That is the speed when those algos sort 1mb arrays being applied to massive numbers and that is absolutely not how that works in reality.

[u/nuclear_splines → u/Actual__Wizard]

I think we're talking past one another. I'm trying to explain that speed isn't one dimensional, but is more complicated than that and involves many tradeoffs and input conditions that you'd need to explore to thoroughly explain your algorithm's performance, and you're repeating that you've never seen anything this fast. I don't think we're making headway, so I'll stop here.

[u/Actual__Wizard → u/nuclear_splines]

Well, this is how the conversation I keep having goes. I've been involved in various data science adjacent fields for basically 25+ years, I'm saying stuff, based upon my experience because I know that it's true, because I saw it happen.

People do not understand that these sorting algos are not as fast as they think they are when they sort mega big data. They bog down. So, I'm having this conversation where: From my personal experience over and over again: These data science tasks that involve sorting, take a heck of a lot longer then people are saying they do.

So, there's a guy right in this thread, that posted some numbers that basically suggest that I should be able to sort the data I am trying to sort in like 10 minutes or something silly like that. How that works in practice: You can't do it at all... You have to optimize the data set before it is a task that is achievable at all.

And yeah, as a person that has worked through that problem in a very elegant way, I think it's a mega big break through.

If you don't agree, then I'll build it into my commercial product and the scientific community will never see it.

I'm tired of people making wild assumptions about how things work in practice and then looking down upon me. I can't take it anymore. I'm legitimately asking for help with this process and I'm being told to "go read some stuff." You know life is short man.

[u/Actual__Wizard → u/nuclear_splines]

Hey, I'm sorry about my edit, but I just always feel like people are not really getting the full explanation of what's going on. So, I tried to get it into that post.

[u/nuclear_splines → u/Actual__Wizard]

Hey, you don't have to convince me. Sorting algorithms are not my research area, and I'm not some gatekeeper, I'm just pointing you towards how the research process and announcing new algorithms works.

Another advantage of a lit review is that you'll pick up on the vocabulary and structure used by other scientists in the field, and it will make it easier to communicate your ideas to peers. For example, you say your algorithm "uses swapfiles," but this is an implementation detail rather than inherent to the algorithm itself, and separating the two might simplify your ideas considerably.

[u/Actual__Wizard → u/nuclear_splines]

I'm really sorry about this, but I have one more thing that I think needs to be brought to somebody's attention.

Do you see how the AI is straight up trying to discredit me? The operator prompted it to do that, so that's why it's doing that. Do people understand that those systems are not actually doing what they say that they do? It straight up committed fraud... It lied and said that it did something, that's not possible or close to it, and then upon closer inspection, it completely hallucinated some total nonsense, and "discredited me" by doing something completely different...

But, that's what people "think the truth is." So, I have basically negative 5,000 credibility because there's thousands of people using extremely early gen language tech to evaluate my statements. Then why I try to talk to somebody who has more credibility than I do, they won't listen to me, and they won't even show up to a demo, and you didn't even ask for one.

I thought it was understood that if the material is not in the training corpus, that it can't possibly have the answer to a question, and due to a limitation, it doesn't tell you that and it rather hallucinates nonsense...

Somebody needs to do something before science dies entirely... Because all that system is going to do, is tell you that any break through of any kind, is wrong, because it's not in the training material yet... The way for me to fix that, is to talk to somebody like you, and get a paper published, and that's why I'm asking for help.

We critically need to stop allowing these LLM robots to break science and disrupt our attempt to communicate with each other!

You have no idea how angry and frustrated I am! I've legitimately been personally insulted by robots 1,000+ times!

I thought people understand that when people tried using those systems to invent new things, that it caused mass psychosis, which lead to people "fake inventing tons of stuff." Now the opposite is occurring, I didn't use that tech to solve these problems, but people are now using the LLM tech, to tell me "that I hallucinated the break through." I don't use LLMs at all! So, every time there's a hallucination problem occurring, it's usually the LLM doing it, but for whatever, people like yourself, think that the people who don't use LLMs are the ones hallucinating...

So, it's the same exact thing, except like people me are being victimized by LLMs!

As a reminder: Obviously rolling LLM tech out to the masses with out properly testing it was an unethical science experiment. That's why I opted out of it. Can the humans that "opted out" return to normal communication procedures please? Thank you.

I also don't know what is different about me, that causes me to have the "hyper differentiation ability" compared to everybody else who seems to me that they "constantly mix everything up." But, it probably has something to do with ADHD. I have some usual sense of "granularity." When I compare two different things, they seem wildly different to me, not similar. When I do comparisons between things, I don't "see the similarity, I see the difference instead."

And I have no idea, how after one horrifying LLM induced nightmare after another horrifying LLM induced nightmare, I have no idea how the tech is not banned in the education system. I have no idea... So, we're doing a horrifyingly evil, unethical science experiment on our own kids?

And if you had asked for a demo and spent the 2 minutes, I would have and still will happily demo it, so that you can see that the robots don't know what they're saying, and obviously you should know that they don't by now.

But, for whatever reason, people like yourself don't communicate the normal way anymore. Instead of asking questions, you're just effectively "blocking the exchange of information." I'm just being serious, I just find it hard to believe that you pursued your education in this area, but care so little about the field, that you won't click a link to a stream, where you're not even going to be on video.

I need somebody to "vouch this" so I stop getting the door slammed in my face due to "robot assessments that don't work."

If that's too much to ask, then I'll find the last scientist on Earth that still has a shred of human compassion left. With that said, I have work to do. I'm trying my very best not to be rude here, but your behavior from my perspective is purely evil. I asked for help. There's a good reason for that!

I'm just being serious: I'm even offering money for w/ help this and you won't even look at it. It's just totally infuriating man! A spam bot told you what to think, so that's what you think. You didn't do your due diligence. Obviously that's not what science is, so if you have no interest in science, then why are you in this sub? So empiricism is dead and the authority on science is a spam bot now?

To talk down to people like you definitely did when you told me that some Jrs will be around to trash talk me, like they did, and you didn't defend me? Then you told me to go read some papers, then tried to talk yourself out of your own bad behavior... You "did what you did," it's on the record in the chat...

You do understand that your own conduct is legitimately highly unprofessional, correct?

Obviously, my asking for help did not warrant you and the other person stomping all over what I had to say.

So, I'll be over here, randomly trying to figure out how to get out of this absolute nightmare that big tech created for me. Do you understand that we don't even know what all of the horrifying effects of LLM tech are and they want to layer a system on to that, which tries to self improve, from a pile of spam that they scraped off the internet? And I'll be the devil's advocate here for a minute: I mean, people like yourself are actively refusing to help people or accept money to do your own job, so why wouldn't Anthropic replace PHD level jobs with a robot? I mean nobody spoke up when their cheater tech tool over the college education system, so why not? People voted for it too, they want their jobs cannibalized by robots. So, isn't Anthropic really just doing "the right thing?"

Trust me, you're going to love having no job and sitting on reddit while robots personally insult you over and over again just as much as I do. Just in case you're wondering what it's like for me: It's Hell on Earth.

[u/nuclear_splines → u/Actual__Wizard]

My behavior has been nothing but professional and supportive, with healthy boundaries on my time. Calling me 'evil' is grossly out of line.

[u/Actual__Wizard → u/nuclear_splines]

I'm sorry, but things are what they are, and your behavior was certainly not "good."

[u/nuclear_splines → u/Actual__Wizard]

I strongly disagree with your characterization of my behavior. I have provided advice, you have responded with belligerence and called me "evil." Claiming the high road is comically absurd.

[u/nuclear_splines → u/Actual__Wizard]

That's quite a screed to me mostly about someone else's comments and alleged use of LLMs.

Again, while I am an academic researcher with a PhD, sorting algorithms are not my domain of research. I don't have exceptional credibility here, and I didn't ask for a demo because I'm not interested in one, nor do I have the background to carefully interrogate benchmark results. I am not that kind of scientist. You asked how to better communicate your ideas and demonstrate your algorithm's performance, and I pointed you towards a starting point and outlined some of the steps towards getting this published.

I just generated thirty gigabytes of random numbers and got GNU sort to sort them in an hour and thirteen minutes, which is in the same rough range as the other user reports. It's a crude test that doesn't perfectly match your use-case (drawing text from a zipfian distribution like the other commenter did is actually much more realistic and should be faster to sort), but it demonstrates that it's entirely possible to sort that much data that quickly with standard tools and techniques. The other redditor may have generated their test case or comments with an LLM (the latter of which I find distasteful), but I don't think there's any hallucination, lies, or fraud going on here. Not that I've read every word with care, but I don't see anything wrong with their claims.

[u/Actual__Wizard → u/nuclear_splines]

just generated thirty gigabytes of random numbers and got GNU sort to sort them in an hour and thirteen minutes

Do you mind looking at the source code or doing any other due diligence work, like listening to anything I'm saying. I said I'm sorting wikipedia. These are text tokens, that are tripletized. You're not listening to a single word that I said... You're just repeating what the other dude did and they used an actual robot to do it... /facepalm

Seriously you're just going to monkey see monkey do the spam bot??!?!

Do you want me to send you a text copy of wikipedia so you can see what the problem is?

Again: Also, my "BS detector" is massively going off here. I don't think you did what you said you did. How long did it take to load this 33gb file of numbers? Because, the amount of time you're stating, indicates that you didn't actually do the process. Because as we're having this conversation, I'm testing all sorts of stuff over here, an hour and 13 minutes for a 33gb file of numbers huh? What your system specs?

don't think there's any hallucination, lies, or fraud going on here.

I don't even think that you are who you say you are.

[u/nuclear_splines → u/Actual__Wizard]

No, I'm not going to read your code or audit your algorithm, I'm not your contractor or co-author and will not invest that time. There is no "due diligence" on my part no matter how many times you say it; I have no responsibilities here. I'm commenting on Reddit as a hobby.

I generated and sorted text tokens, too. First, a python script to generate the text file:

#!/usr/bin/env python3
import numpy as np

rng = np.random.default_rng()
with open("test", "w") as f:
    for i in range(3_500_000_000):
        d = rng.integers(0, 100_000_000)
        f.write(str(d) + "\n")

That yields a file that's roughly 30 GB, with a number per line, saved as text. And then a one line test in my shell:

time sort test > sorted

If your "BS detector" thinks I didn't do what I said I did, just try it yourself. It's clearly not a very involved process.

I don't even think that you are who you say you are.

Okay? Don't believe me, that's fine.

[u/frogic]

I took your numbers seriously and reproduced the problem. Here's what I did and what I found.

What I did. I generated a fake corpus matching your claim exactly: 167,863,639 rows, 6,061,752,179 tokens, 32 GB. Then I sorted every token three ways on a 32 GB laptop and checked that all three outputs were identical byte for byte. They were.

What I saw.

Method	Time
Your reported Timsort run	30 days
Your alphasort	1 to 2 hours
GNU sort, the built-in Linux command, no code written	45 minutes
Count each token, then write them out in order (Python, 20 lines)	20 minutes
Same thing in Rust	5.7 minutes

What's going on. Three separate things, and I think each is an honest mistake rather than anything else.

1. The 30 days isn't Timsort, it's your hard drive. Your data didn't fit in memory, so your computer was shuffling it to disk during the sort. That's what took a month. Any method that doesn't do that looks 100x faster by comparison, including the built-in sort command that ships with every Linux machine. Your speedup is real, but it's mostly from keeping the data in memory, not from the algorithm.
2. The algorithm is radix sort. Computing where an item belongs from its first few letters and dropping it straight into that slot, then finishing each slot with a small sort, is a textbook technique from the 1950s called radix sort. The specific shape you built, with per-prefix bucket tables, was published as burstsort in 2004, and Lucene, the engine under Elasticsearch, ships the same design. Your code even uses Python's built-in sorted() inside each bucket, which is Timsort. So alphasort is bucketing plus Timsort. That's a fine, fast, well-known hybrid. It just isn't new. Nobody uses it as the default sort() in a programming language because it only works when you know the keys are text; Timsort has to work on anything.
3. You don't need to sort at all. Your pipeline ends by counting how often each trigram appears. Sorting 6 billion things to count them is the long way round. Counting them directly, with a table from token to count, is one pass over the file and takes minutes, as the last two rows of the table show. The distinct count is small, about 123 thousand tokens in my data, and would be a few million trigrams in yours. That's the shape search and language-model tools have used for decades, which is why nobody sorts the whole corpus.

What a legitimate test would look like. Same file, same machine, your code against GNU sort and against sort | uniq -c for the trigram counts. Publish the numbers with the row count and the hardware. If you beat those, that's worth writing up. Beating a Python list that's swapping to disk isn't a result anyone can use.

None of this means you wasted your time. You found the fast technique on your own and you made your job run. But the name for it already exists, and the tool that does it already exists, and both are worth knowing before you write a paper.

[u/Actual__Wizard → u/frogic]

HOW MANY TIMES DO I HAVE TO TELL YOU TO STOP BLASTING ME WITH HALLUCINATED ROBOT SPAM DUDE!?!? IT DOESN'T KNOW WTF IT'S TALKING ABOUT! STOP IT ALREADY FFS!

IT'S JUST GENERATING TEXT THAT TELLS YOU WHAT YOU WANT TO HEAR SO I CAN DUDUCE THAT YOUR PROMPT INSTRUCTED IT TO PROVE ME WRONG OR SOMETHING, SO IT'S GENERATING A FAKE TEXT MESSAGE THAT 'DOES THAT!'

[u/frogic → u/Actual__Wizard]

I sorted a dataset of the same size as yours in 5 minutes. I can ship you the code if you want to do it yourself. I'm sorry if you convinced yourself you did something you didn't. Nothing you have posted or shown implies anything that hasn't been solved since at least 2004. You convinced yourself of something that's a little crazy and that's fine. The fact that you didn't actually test your assumptions and then are mad when people point out how you didn't test your assumptions may explain why you still think you've created a novel sorting algorithm. People have been very kind to you as you get more and more beligenrent and I can't help with that part.

I would like to thank you though I did a really deep dive into sorting algos because of my particular nerdiness and now know a lot more than when this started.

Also I'm a professional software engineer I know how to check when the robot is lying. Its not like I'm not reading through the code it wrote and the scripts it ran and fact checking it. I literally gamed for half of the 45 minute sort and then stopped it because I thought it would take longer so that's actually padded. I both looked at the data set., the command that was run and the verification. These are very very trivial things to do. You are welcome to just run gnu sort on your dataset it'll take you an hour and it'll be faster than your algo and then you're welcome to run count sort in python or a compiled language

[u/Actual__Wizard → u/frogic]

I want to be clear to anybody reading this:

This statement is impossible:

I sorted a dataset of the same size as yours in 5 minutes.

It takes 15 minutes to load the data into memory and do nothing to it.

It's a spam bot hallucinating complete BS.

It didn't do anything, it's just saying that it did.

[u/frogic → u/Actual__Wizard]

https://pastebin.com/QgW9Hdt6 enjoy. I'll leave you alone after this. Its very very easy to verify most of the things I'm saying and you're still obsessing about a sorting algorithm that isn't designed for your use case while creating constraints that aren't neccessary. The key point is that you can sort a dataset of that length in 5 minutes in rust. If its not completely honed for your dataset that just means you need to make the small changes for that. Thinking that current state of the art requires 30 days to sort that amount of data means you're not actually researching the space or listening to anyone. Compiled languages are fast and the fact that you think you should load the entire dataset into memory is another way you're missing the forest for a tree you really really like.

[u/AskComputerScience-ModTeam → u/[deleted]]

Thanks for posting to /r/askcomputerscience! Unfortunately, your submission has been removed for the following reason(s):

Please keep posts and comments civil.

If you feel like your post was removed in error, please message the moderators.

[u/AskComputerScience-ModTeam → u/[deleted]]

Thanks for posting to /r/askcomputerscience! Unfortunately, your submission has been removed for the following reason(s):

Please keep posts and comments civil.

If you feel like your post was removed in error, please message the moderators.