Try making more videos on simple things expanded upon I’d say for more views. Your colors, first sorting video, and Platonic solids video were hits, and they all follow the “here’s a basic topic you already know about, I’m about to explain something complicated you didn’t know about it”

Thank you! That is some really smart advice!

I have a question, can we create say, a joke-sorting algorithm that works in prime number time. This means that the number of operations is O(p_n). I mean it is proven that p_n ~ n*(log(n)+log(log(n))-1) for n>=6. Note that here log represents log base e not 2.

@@pokemonjourneysfan5925 that's really interesting! I've never seen a sorting algorithm that is O(log(logn)), but I've heard it's theoretically possible if the input is only integers.

@@Kuvina More specifically I said, it runs in Prime number time. p_n is the nth prime.

I don't think local variables count against space complexity, as long as they're not arrays of a size dependent on n. You have to be able to swap stuff, after all. All the pointers and partitions, etc are part of that.

​@@DFPercush en.wikipedia.org/wiki/XOR_swap_algorithm :P

I mean, they technically do. But if it's just "And a temporary variable for swapping things", that's O(1) extra space. Contrast with a normal merge sort that needs a buffer the size of one of the blocks to be merged, which is half the size of the array or O(n)

What you propose would obviously lead to enormous savings when sorting, for example, a huge number of integers on a specific machine. But I think what you usually have is at most a few thousand elements sorted on a more or less random CPU (little more than the architecture being fixed) with somewhat random cache sizes and the actual comparisons delegated to a function or macro of variable complexity. In that case you don't know what to optimize for, and whatever happens during the comparison calculations may well completely destroy your locality. The usual metric of number of comparisons is exactly right in this case.

My beloved HeapSort shall be avenged.

From benchmarks I recall seeing (awhile ago, no links, sorry), they're surprisingly competitive given the complexity involved. I suspect that a good quicksort will be faster on random data, but given the drawbacks of quicksort (unstable, hard to pick a good pivot for non-random data), they are probably worth considering. I believe wikisort is now used in some standard libraries.

quicksort is unbeatable considering cache efficiency.

Yes, a good set of benchmarks would help. Performance will depend on the size of the input and blocks, and which variant of block sort of course. There are some benchmarks for block sorts like quadsort, octosort and wikisort vs glibc qsort and std::stable_sort. Quadsort wasn't quite a fair comparison since it seems to use extra memory -- it is very fast but the author acknowledges "Quicksort has a slight advantage on random data as the array size increases beyond the L1 cache". Octosort seemed comparable to qsort for fully random order but much faster for a few scenarios (esp. already sorted ascending/descending). Wikisort is similar, but may not be as useful in embedded / low-memory environments because it slightly bends the "rules" by using a fixed-size 512-item cache -- this is still technically O(1) space because it's a constant size cache, but may not be what you want.

I think it's from a video called something "the song of the world" but i'm sure it's from a channel called "midi music"

07

kzfaq.info/get/bejne/qrFhgJlom8eUh40.htmlsi=7BXe6TAdIIGSdQmX

RIP

-yes😂bo-

That task is usually solved by quicksort, you just don't sort both halves recursively, only the half containing the k-th element to find k lowest elements.

Which is known as "quick select".

Alternately, a Heap automatically maintains the smallest value at it's head, and has log(n) time for getting the next smallest item.

@@Milan_Openfeint I haven't benchmarked it, but the worst case time complexity for this algorithm is O(n²). My worst case time complexity is O(n). The only benefit I can think of is that it would make the second selection O(1). But that seems overkill for just grabbing two elements. In all honesty, I did think about trying quicksort, but the thing that stopped me was that the one library I found for it used a lot of memory allocations, which was already taking most of my time.

If you just need to find the k-th largest/smallest value (in your case k=2), consider using quick select. Quick select is O(n), in-place, though not stable. If you write C++, it is called "std::nth_element" The resulting list's first k elements will be the k smallest elements, and the k-th element in the list will be exactly the k-th smallest element. If you then need the first k elements sorted, you only need to sort the first k-1 elements however you want, or if k

as an enby i can confirm

I think it's basically like rotation based merging, but in reverse. So in the algorithms where the left sublist is already sorted, you just start at the beginning and repeatedly find the first piece that is greater than the last one you used, and then rotate it into the next spot in the buffer. As for grail sort, you can use basically binary insertion sort, but if you find that the piece is exactly equal to one of the ones already in the buffer, you simply skip it and don't insert that one.

Honestly I'm not sure. I don't know how you could do it faster, but I wouldn't be surprised if they found a way.

Thanks that's a good point! I should have mentioned just because it checks the boxes doesn't mean it's necessarily the most practical algorithm for every purpose!

@@KuvinaWell, the big-O notation is always very deceiving. I usually tell people the story, that I required a lookup table for network protocol implementation in a system kernel. What did I choose? Well, a hasthable, of course, as it is O(1). Years later and just out of curiosity, I wanted to see what happens if I replace the hashtable by a sorted array instead, where lookups are O(logn), of course (binary search). And the result was: The sorted array resulted in a significant better performance. Of course, there is a turning point. The array will get slower the more elements it has, whereas the hashtable will roughly stay the same. I was able to calculate the turning point and later benchmarks confirmed that calculation to be correct. But that turning point was irrelevant, as it was way beyond 256 entries and the lookup table was bound to having at most 256 entries (the table entry count was stored in a byte) and would typically not have more than anything between 4 and 64 entries in real world scenarios. So just because two algorithms are both O(nlogn) and both have O(1) space complexity, doesn't mean it's totally irrelevant which one you pick. If there were no advantages and disadvantages, then there would be no reason why different variants even exist, right?

@@xcoder1122 When it will have at most a small bounded number of elements, like 256, it's also worth considering just using a bitmap + the data (if the data has some kind of null state, you can also avoid the bitmap) and get lookup in a single pointer offset. It uses a bit more memory, but if this is a persistent structure that multiple copies won't exist of that's not much of an issue in most cases. Unless you're using a 16-bit microcontroller or something, anyway.

Each time you rotate, you need to move O(sqrt n) elements right and possibly O(n) elements left. This is done O(sqrt n) times in total, so it seems like it will take O(n sqrt n) time in total. But notice that each element is shifted left only once. This means that the time complexity of shifting elements left is O(n) in total. We shift O(sqrt n) elements right a total of O(sqrt n) times, so the time complexity of that is O(n) in total. Thus, the full merge process is linear.

@@vgtcross But how should this algorithm be implemented, like keep shifting the next element after the sublist until reaching the destination? But if so then wouldn't it be shuffled and will need to be sorted every time it shift?

So a rotation of 2 sublists can be done in linear time (compared to the length of the 2 sublists) if you simply flip each one then flip them together. This moves each piece twice, and there are faster ways that move each piece once, but the same time complexity.

It requires O(logn) stack space for the recursion

@@canaDavid1 And it's not guaranteed to be O(logn) time (nor space) complexity, that depends on choosing "good enough" pivots

In the future, we will probably have 1 quadrillion parameter AIs that are actually useful for this. Maybe we will have them sorting something that can not be sorted easily, like quatum entangled particles.

If we are going to have that strong AIs I don't think sorting anything will be a problem@@simonwillover4175

That's basically the "Universal Search" algorithm. Ironically, it's the "absolute fastest" of all algorithms from the perspective of complexity theory, even though it's horribly slow. That's because the time to build "the AI", or whatever you call it, is CONSTANT, and thus negligible compared to O(n).

@@user-qm4ev6jb7d so if we had to sort like a list of 10^1000 items, the evolution sort would probably be pretty effective!

Most sorting algorithms don't work well if you can't arbitrarily swap elements.

for uneven record lengths you can store a fixed length header followed by a pointer to the rest - most of the comparisons are decided by the header.

alternatively you can treat the header ties as their own sub-sorting problem - rows with the same header get sorted together, then you can do a second pass to 'tie-break' grabbing a second header chunk out of each group of ties.

It can be with hyper large lists, like more than would fit into RAM (external sorting). External sorting is another can of worms anyway. But it would likely be something like doing a sort on blocks of a certain size where a standard algorithm would be able to do it in RAM, then use extra space and in a streaming fashion perform a (potentially n-way) merge sort.

so the thing about insertion sort is that even though you can find a piece's destination within the sorted section in O(logn) time, to actually get it there, you have to shift everything over. On average, you have to shift over half the sorted section, which is on average half the list, so inserting 1 piece, even with a binary search is O(n) per piece, therefore in total it's O(n^2), the same time complexity as regular insertion sort. (It does have fewer operations though, just not a time complexity difference)

According to Andrei Alexandrescu, binary search insertion sort is also worse experimentally, since the branches are less predictable. In the linear insertion sort, the CPU can learn that most of the time, the inner loop is continued, but in binary search insertion sort, you can take the upper or lower branch seemingly at random. Branch prediction matters!

@@nullplan01 That's weird. How would e.g. 15 unpredicted outcomes be worse than 8000 loops?

@@iwersonsch5131 if the branch is mispredicted, the effect is a pipeline flush, which can be as bad as doing nothing for hundreds of cycles. Plus Kuvina already explained that you still need the linear move operation.

@@nullplan01 So linear insertion sort has 1 pipeline flush per entry, while binary insertion sort has about lb(n)/2 pipeline flushes per entry. A middle ground could be to break up the sorted list into linearly searched blocks of, say, sqrt(n) (or for very large n, n^(1/3) and n^(2/3)), resulting in 2 pipeline flushes per entry, or 3 for very large n, while keeping the comparisons for each entry below 1000*log_1000(n)

O(n log n) is always higher than O(n), but it doesn't matter because it's optimal for comparison sorting. O(n) comparison sorting doesn't exist. Also, log n grows so slowly that the difference barely matters anyway. By the time it log n is appreciably large, you're hopefully going to be using a parallelized sort instead.

I don't know the proof, but that's a good idea!

@@Kuvina awesome!

There are n! possibilites that the array can be in. Any comparison only gives 1 bit of information, but one needs log(n!) in total. n! ≈ n^n, so log(n^n) = nlog(n) is a lower bound on the number of comparisons needed to figure out what the permutation is.

​@@canaDavid1n! Isnt about equal to n^n though, in fact n^n > n!.

​@@jetison333log(n!) / log(n^n) asymptotically approaches 1 though, so they both evaluate to n log n in O notation

Implement, benchmark, give up.

@@Milan_Openfeint Well, today sorting is result of years of optimize. Can't beat that easily. My idea can sort everything in two part. Read from main array once and get multiple sort lists. Then combine that lists to main array. Part 2 Multi thread able. And result is Stable. ... With big memory usage problem

Quick sort is O(logn) space due to recursion, which is sometimes considered in place, but usually only O(1) is considered in place

Thank you knots and Himari!

Personally I wouldn't say that. Radix sort doesn't really have any type of block rearrangement or local merging. It does categorize pieces into groups, but I would say radix sort is a type of bucket sort or vice versa. I would instead classify block sort as a type of merge sort.

Because you might be sorting complex objects which have multiple keys. If you sort a list of people by age, you don't want the list to change relative order. If you did, it wouldnt be possible to guarantee a sort of two different keys since sorting by the second key could break the ordering of the first key.

@@platinummyrr Yes, stability matters

// Data Set size: 32768 x 32768 - RTfloat ///////////////////////////////// Application - MgwTestApp - NOS64_MGW ( 64-bit ) - Release Tests: Start Command Line arguments - User Count : 6 Values: 32768 3 1 4 7 * Test0001 Start * Microsoft Visual Studio version Not Defined ********************************************** Configuration - NOS64_MGW ( 64-bit ) - Release CTestSet::InitTestEnv - Passed * CSortSet Start * * TSortSet Methods * * CSortSet Methods * GetSortOrder - Passed Data Set of RANDOM Values Data Set Size : 1073741824 elements Number of Iterations: 3 Number of Tests : 1 Number of Threads : 4 * CSortSet Algorithms * Data Set: RTfloat - in RANDOM Order GetSortOrder - Passed HeapSort - Sorting... HeapSort - RTfloat - 425415.00000 ms HeapSort - Passed QuickSort - Sorting... QuickSort - RTfloat - 10495076.00000 ms QuickSort - Passed MergeSort - Sorting... MergeSort - RTfloat - 146345.00000 ms MergeSort - Passed Data Set: RTfloat - in ASCENDING Order GetSortOrder - Passed GetSortOrder - RTfloat - 0.00000 ms GetSortOrder - Passed * CSortSet Algorithms - VALUESET * Converted to RTdouble type Converted to RTubyte type VALUESET:RTubyte - 0.00000 ms VALUESET:RTubyte - Passed * CSortSet Generic * * CSortSet End * * Test0001 End * Tests: Completed

You really need to Re-Think of everything when there is a data set of 1 Billion elements. Your "toy-test-cases" with n=300 Absolutely Small!

yeah I should've specified, nlogn is optimal for comparison based sorting algorithms if you don't use parallel processors.

I can't tell if you're being rude or if you're comedically signing the comment as if you're a "PoS"...

​@@animowany111/pos means positive connotation

@@noelletheradcat Huh, never heard of it. The acronym for "Piece of Shit" (or "Point of Sale", but those are basically the same thing lmao) is too ingrained in my head

How does it work for arbitrary size of each element?

You can only sort an arbitrarily-ordered array in linear time if you know the *distribution* of the data beforehand, otherwise the minimum complexity will be O(n log n).

@@Musicombo In almost all practical cases, values are stored in 32, maybe 64 bit integers, which can always be sorted in linear time. If you don't make that assumption, then yes, you are right.