An understated benefit of merge sort is that all of its access patterns have excellent locality. Regardless of big-O, this is a huge advantage because it reduces cache thrashing.
Like it probably doesn't matter if you're sorting 10k entries, but when you're sorting several gigabytes it really does.
Quite the opposite. Merge sort is much more susceptible to cpu cache misses. You have to go out of your way to optimize mere sort to avoid cache issues. But the devil is in the details and it really depends on the arch, the dataset you're sorting (numbers vs strings makes a big difference), cores and cache levels available, memory available.
In practice, to avoid worse case quadratic time, you have to have a rather involved pivot selection in Quicksort. Eg nine random or evenly distributed elements which you put in three groups of three and take the median of the median.
Collecting those nine elements looks terrible for locality.
Funnelsort is a cache oblivious variant of merge sort which is provably cache optimal in some sense. I haven't tried implementing it.
To handle quadratic edge cases you would switch to heapsort when the recursion depth goes above the threshold. I.e. introsort; no need for convoluted pivot selection methods.
That's usually called Introsort, but I think you'll find that most of these still consider at least the middle element for a pivot, so they still have a more complex cache behaviour than the naïve linear sweep from both ends of a simple Quicksort.
I like to think so but I'm not sure that's true. At least I don't think I've ever seen anyone divide a stack in half, then divide the left one in half, then divide the left one of that in half, etc. as if they're doing recursive mergesort. I feel like most people start from the first card and build upward, either with insertion sort or with something like iterative mergesort.
I think most people would shortcut the "recursive task-spawning" part by just taking all the pages and spreading them out individually side-by-side on a work surface.
That's why I said it's like the iterative version of mergesort, which goes bottom-up. People don't divide things in half like in traditional recursive mergesort, is what I was saying.
What I’ve done is: Grading data structures exams (appropriately enough), I’d grab a handful of them, and grade them, and then sort the little stack. Then I’d put it aside to deal with later.
Eventually I realized I was running out of desk space, so I started merging little stacks of around equal size.
So the base case wasn’t 1 element, but that’s conventional for actual implementations. And the splitting wasn’t quite recursive I guess. But partial credit at least.
Only for reasonably small stacks. Insertions at random indices won't stay O(1) when you're dealing with 100k pages and more – i.e., when you can't pick them up in one movement.
When I taught, I would sort graded papers/tests using quick sort. Put all the a–l in on pile and m–z in the other, then do each pile into halves and manually sort the quarters. And since I knew what the sorted set looked like, finding pívot points was trivial.
Merging stacks of papers by hand isn't the same as exchange-based computer mergesort: if the cost of inspecting and comparing items is negligible relative to actually moving them the basic, unit cost operation is splitting a sequence into three possibly empty sequences and splicing the middle piece into an arbitrary position in another sequence. In some cases reversing the spliced sequence is free ("pancake" sorting).
This cost model is an important reason to merge bottom up, from sorted subsequences, without arbitrary splitting that can add work but not reduce it.
At one point I used to work at a place that had a production process that used several hundred ibm 3480(if I remember correctly) tape cartridges. I would do a LSB radix sort afterwards to get them back in order.
I think back on it with a certain amount of nostalgia now, but it was a stupid way to do operations, even at the time, They had invested big in computers in the 70's and were still maintaining the same tech stack in the early 00's when I worked there.
Locality is good during merge but there’s no parallelism - there’s a data dependency between the previous and next iteration because we don’t know which pointer we’re supposed to advance. I think it’s still unclear whether this necessarily is compensated for by the cache locality
I am curious about exactly what v8 was doing at the time, because "just use Quicksort" doesn't work for inconsistent comparison functions or mutating data. These issues aren't magically resolved with "use a stable sort", but it means you're not just calling qsort(...) to perform the sort.
I vaguely recall JSC actually having a literal tree sort at one point to deal with this.
If you provided an inconsistent comparison function I don't see how it's the sort implementation's responsibility to produce a sensible output. Or even to terminate at all.
This is in a JS engine, where by design all code is untrusted.
If you are a JS engine, then arbitrary code execution, failure to terminate, or crashing is never an acceptable outcome, regardless of how bad the code is, because again, you're dealing with untrusted input. The assumption for a JS engine is necessarily that all code is malicious.
Obviously it may never crash, and it never did, even with a bad comparison function.
But the JS engine does not protect against the page containing JS code that loops forever. How would it even do that?
Edit: Perhaps some misunderstanding: V8 "just used Quicksort", but it never used the qsort function from the C library. That would not have worked with garbage collection, since you can have a garbage collection in the middle of sorting, which could move the array.
Prior to chrome every browser had a “terminate js after x seconds” option that didn’t mean “kill the process”.
But the point is that the general quicksort algorithm does a bunch of unsafe memory accesses if the comparator is unstable (either directly or by modification of the sorted data). As demonstrated by every qsort implementation going wrong in unsafe ways in such a scenario.
Now maybe you used a version of qsort that actually made sure it wasn’t going out of bounds and what not and did … something? When that occurred, and saying what that something was would be a reasonable answer.
As for qsort() not being an option due to gc, that’s only a problem due to v8’s gc - JSC for instance could just use qsort or what not if it was sure the sort was consistent.
V8's Quicksort was written in JS so going out of bounds on an array access did the same as it would in any other JS program. As I recall, JS isn't super helpful about out of bounds accesses, but there's nothing memory-unsafe about it.
> Recently, Timsort has become popular, also a variation of Merge Sort. However, Timsort was not invented yet in 2008.
Timsort is from 2002. Not sure where this comes from. Perhaps it wasn't as popular or widely known in 2008 as it is now, but I actually learned about it at about that time. See also:
(edit: timsort was introduced to Java in 2009, per https://bugs.openjdk.org/browse/JDK-6804124, and knowledge of it would probably have spread much further from that point, so maybe that's the source of confusion?)
I used Timsort in a class around 2010 and it had been in Python for “a long time” at that point. I also tripped on this article’s claim that it didn’t exist yet in 2008.
Note that it is straightforward to modify an unstable sort algorithm into a stable one, when it’s okay to use O(n) extra memory: define an array that tracks each element’s original position, and when two elements otherwise compare equal, use the original position as the final tiebreaker.
(With that said, Timsort must be faster in practice than this kind of retrofitted unstable sort. I’m curious how large the difference is.)
That's my usual approach, but there are clearly some programmers who don't want to always do this, and sometimes a stable-sort library function does in fact allow them to be more productive.
This seems basically equivalent to saying that whether or not a sort is stable is irrelevant, right? If the position of elements with equal keys doesn’t matter for your application, then of course there’s no reason to use a stable sort (or convert a non-stable one to stable by whatever trick).
I'd assume cache locality makes it worthwhile, especially if the keys are big, point to big things that need to move, or live on separate drives. To that last point I'd wager stable algorithms can imply parallelization.
If you can digitize it, you can probably sort it, that's true. But the sort keys can get very artificial and weird.
Let's say you're sorting a bunch a unlabelled images. You can sort them by number of pixels, that's pretty clear but will likely have clashes.
You could then sort by either width of height next, but the choice is pretty arbitrary. It's not obvious why a 100x10 pixel image should come before or after a 10x100 pixel image. But it's not very weird to pick one either.
Next you could sort on properties of the first pixel. But those are multidimensional. Sorting by the most red first, for example, would be weird.
You could still create an ordering if you need the consistency, but it wouldn't mean anything.
If you don't sort by them, you can get images that are different in ways that aren't sorted. Stability (well, instability) becomes detectable.
If you have to use an unstable sorting algorithm you'll be stuck choosing between images jumping around or being in a certain spot because the 34th pixel on the 56th line is slightly more greenish than in the image before it. It can depend on your use case which of those is least desirable.
Having a stable sort would give you another option.
Deeper comparison doesn't solve the problem because input order is arbitrary. The order may be based on a user dragging items around in a list widget, for example.
The easiest way to transform an unstable sort into a stable sort is probably mapping input from T -> (Index, T) and including the index as a sort key.
I'll spell it out then: you don't always need to sort based on the entire object's value. Comparing the whole object can be pretty expensive when you only need to sort by one field.
I didn't expect to learn something new about sorting while reading this. It's really cool that you can do Merge Sort asymmetrically, which lets you use a scratch buffer only 1/4 the size of the original array.
At FOSDEM 2023 I will be presenting glidesort in the Rust room.
It is a new stable sorting algorithm that is a hybrid of quicksort and mergesort which is much faster for random data, while still taking full advantage of pre-existing order or inputs with many duplicates. On an Apple M1 in Rust the latest version is ~4.5x faster than the stdlib slice::sort for sorting 2^25 random integers while using 4 times less extra memory. It is 11.5x faster if you happen to sort only 4096 distinct integers with many duplicates. Note that the algorithm is purely comparison based and does not contain special type-dependent SIMD stuff.
Those numbers look impressive. For stuff like this, can it be said that it should just be implemented as is in the std libs of mainstream languages like Java, Python, C#?
For C#, it is very similar to Rust, so I would say yes. I'm too unfamiliar with the JVM and its performance characteristics to say for sure for Java, but probably also yes. However, the performance characteristics of Python are so different to Rust that I think it's safe to say a different approach will likely end up better (one that focuses on minimizing indirections and comparison function invocations).
Hey, the open source release will coincide with the FOSDEM presentation, so in a little under three weeks it will be under my Github account github.com/orlp.
Radix sorts actually can be used with many custom comparisons by using a sort by api which is enough to let you express many of the uses of custom sorting (e.g. sorting objects by fields, sorting by absolute value, etc). Given the overhead of radix sorts, it wouldn't shock me if this was faster for small sizes.
A number n is bit reversed if it is written was written in binary (base 2) and then the bits were written in reverse order.
Last time I looked at Shell sort, when sorting n records on keys in bit reversed order, the iterations of Shell sort did nothing until the last iteration at which time Shell sort was just bubble sort or some such and, whatever, ran in time O(n^2) where the O() is some obscure but now common notation. The article claims something smaller than O(n^2). Okay, but to get something smaller, have to tweak what used to be a standard version of Shell sort.
For another point, the article wants a stable sort -- if two records (the data being sorted) A and B have equal keys and before the sort record A is before record B, then after the sort record A will still be before record B. But, if want a stable sort, then for one approach, before the sort, number the records and use these numbers as part of the keys. Right this extra step runs in time O(n) and uses extra temporary, working storage proportional to n. For current computing, is this extra storage a meaningful issue?
I wonder which type of Shell sort you were looking at. In my experience, it is fairly simple to implement gap sequence that is faster than O(n^2). Sure it is not a stable sort. But it is really simple (a few lines of code), doesn't use recursion, and is fairly fast. In fact, I'm not aware of an algorithm that is as simple as Shell sort, and at the same time much faster than O(n^2).
> In fact, I'm not aware of an algorithm
that is as simple as Shell sort, and at
the same time much faster than O(n^2).
My favorite is heap sort, guaranteed O(n
log(n)) average case and worst case, meets
the Gleason bound and, thus, is the
fastest possible sort based on comparing
pairs of keys (in one of volumes of D.
Knuth, The Art of Computer Programming).
You mentioned simple: The logic of the
heap data structure and its corresponding
code seem to be relatively simple.
Of course, radix sort does not work by
"comparing pairs of keys", may be regarded
as O(n), and, check this, may also be
stable. Of course, radix sort was the
algorithm of the IBM punched card
sorting machine so maybe goes back to
before 1900 and, thus, is likely the
oldest of the common sorting algorithms.
Below (in a separate post) is code for
ai_heap_sort02
which is an (ascending integer) heap sort
routine.
Right, this code is for only ascending,
integers, and arrays and, thus, is far
from the practice of generic code, e.g.,
as in
The advantages of generic code my work
doesn't really need. Once I wrote some
generic code, and that experience was
enough!
The code is in Microsoft's Visual Basic
.NET.
Why Visual Basic .NET?
I have written some C code. There are
claims that the programming language C has
idiosyncratic syntax. Whatever it has,
I don't like its syntax. I.e., supposedly
i = ++j+++++k++
is legal -- increase j and k by 1, add the
results, assign the result to i, and then
increase j and k by 1 again -- but when I
tested this on two different C compilers I
got different results. If the compilers
can't agree on the syntax, I don't want to
try to understand it! Besides, C is
supposed to be really simple, close to
assembly language, and highly portable,
and ambiguity I observed for
i = ++j+++++k++
conflicts with those attributes! Besides,
that syntax gets the grand prize for not
just idiosyncratic but obscure,
ugly, outrageous,
etc.!
Maybe C and C++ are essential for Windows
internals and for Windows applications
that make direct use of the System32 API,
but I've never written such code since my
background is applied math software.
Thus, also I don't like the related syntax
of C++ or C#.
The syntax of Visual Basic .NET (VB) is
more traditional, more like the original
Basic, then Fortran, Algol, Pascal, and
PL/I (maybe my favorite).
Thus, VB is relatively easy to teach,
learn, read, and write, and these
attributes might be considered important
in a large project!
Whatever the syntax of VB is, there are
claims that VB and C# have equivalent
semantics and differ only in syntactic
sugar. I.e., supposedly there is a
source code translator program than can
translate code in either of VB or C# to
the other.
So, for my project, code to run on
Windows, I am writing in VB instead of C#.
Also below (in a separate post)
is code
Function obj_heap_insert
Here I use the heap data structure, the
main idea in heap sort, to maintain a
priority queue. So, with this code can
look at 20 million objects one at a time
and end up with, e.g., the 20 largest.
Uh, how else to do that???!!!
Right, this code starts to be a little big
generic.
Right, operating on the heap data
structure can hurt possibly desired main
memory and cache memory locality of
reference, but there is at least one
modification of modifying operations on a
heap that speed up what otherwise might be
the case of a heap large enough to need
virtual memory.
All this code appears to run correctly. I
have later versions modified, longer, less
easy to read, to use an error handling
technique I cooked up -- really simple, I
wouldn't recommend for larg...
' Ascending integer (Int32) heap sort.
'
' For i = 1, 2, ..., n, sort components of key_array(i)
' into ascending order using heap sort.
'
' We check parameters for reasonable values and, in case of
' a error, raise the error condition.
'
' Upon return, for i = 1, 2, ..., n - 1,
'
' key_array( i ) <= key_array( i + 1 )
'
' The code here is 'structured' in the sense of E. Dijkstra
' and, thus, is without the GOTO statements of own Watson
' PL/I heap sort code.
'
' The array subscript logic here is done carefully enough
' that it should never overflow even for the largest
' possible value of n.
'
' For some constant k (depending on the computer, compiler,
' etc. but not depending on the parameters) the execution
' time is guaranteed to be closely just
'
' k*n*log(n)
'
' in the worst case.
'
' The code here needs a 'sift' loop in two places; the code
' is the same in both places.
'
' The work here is 'in place', that is, uses no storage
' whose size depends on the passed parameters.
'
Sub ai_heap_sort02( _
ByRef key_array() As Int32, _
ByVal n As Int32 )
Dim routine_name As String = "ai_heap_sort02"
Dim error_code As Int32 = 0
Dim i_2 As Int32 = 2
Dim i_first, i_middle, i_last As Int32
Dim i_father0 As Int32
Dim i_father, i_child1, i_child2, i_max_child As Int32
' We need one working location of data type the same as the
' components of parameter key_array():
Dim key_father As Int32
Try
' Get started:
error_code = 1001
If n <= 0 Then err.raise(error_code, routine_name)
error_code = 1002
If key_array.GetUpperBound(0) < n Then
err.raise(error_code, routine_name)
End If
error_code = 1003
i_first = 1
i_last = n
i_middle = i_last \ i_2
i_father0 = i_middle + 1
' Build heap
Do
i_father0 = i_father0 - 1
If i_father0 < i_first Then Exit Do
key_father = key_array( i_father0 )
i_father = i_father0
' Sift
Do
If i_father < i_middle Then
i_child1 = i_father + i_father
i_child2 = i_child1 + 1
If key_array( i_child1 ) > key_array( i_child2 ) Then
i_max_child = i_child1
Else
i_max_child = i_child2
End If
If key_array( i_max_child ) > key_father Then
key_array( i_father ) = key_array( i_max_child )
i_father = i_max_child
Continue Do
Else
key_array( i_father ) = key_father
Exit Do
End If
Else ' i_father >= i_middle
If i_father > i_middle Then
key_array( i_father ) = key_father
Exit Do
End If
i_child1 = i_father + i_father ' i_father = i_middle
If i_child1 < i_last Then
i_child2 = i_child1 + 1
If key_array( i_child1 ) > key_array( i_child2 ) Then
i_max_child = i_child1
Else
i_max_child = i_child2
End If
Else ' i_child1 = i_last
i_max_child = i_child1
End If
If key_array( i_max_child ) > key_father Then
...
You are right, heap sort doesn't need recursion, and is more efficient than shell sort for large arrays. But if you compare the code size, it is hard to beat shell sort. This is a Java version:
static <T>void shellSort(T[] a, Comparator<T> c) {
int n = a.length;
int h = 16, g = 1;
while (n > g) {
h = h + h + h / 4 + 16;
g = (h + 15) / 16;
}
do {
h = (h - 16) * 4 / 9;
g = (h + 15) / 16;
for (int i = g; i < n; i++) {
T t = a[i];
int j = i;
for (; j >= g && c.compare(a[j - g], t) > 0; j -= g) {
a[j] = a[j - g];
}
a[j] = t;
}
} while (g > 1);
}
I was wondering, is there anything as simple as that, and similarly efficient? I doubt it.
' Function obj_heap_insert
' Object heap insert to use the heap algorithm to maintain
' a 'priority queue'.
'
' So, suppose for positive integer n we have x(i) for i =
' 1, 2, ..., n and for positive integer m <= n we want the
' m largest of the x(i). So, we allocate an array y(j), j
' = 1, 2, ..., m.
'
' Suppose we regard y as an ascending heap, e.g., so that
' y(1) <= y(j), j = 2, ..., k <= m where the number of
' locations of y in use so far is integer k where 0 <= k <=
' m.
'
' Then for i = 1, 2, ..., n, we consider inserting x(i)
' into the heap.
'
' If k < m, then we set k = k + 1 and set y(k) = x(i) and
' 'sift' to 'promote' the value in y(k) until we have a
' heap again.
'
' If k = m, then we compare x(i) and y(1). If x(i) <= y(1),
' then we are done with x(i). Else, x(i) > y(1) and y(1) is
' not among the m largest and, to 'remove' value y(1) we
' set y(1) = x(i) and 'sift' the value in y(1) to create a
' heap again.
'
' After i = n, y contains the m largest of x(i), i = 1, 2,
' ..., n.
'
' The advantage of this routine is speed: When k = m, the
' effort to insert x(i) is proportional to log(m). When k
' < m, the effort to insert x(i) may be proportional just
' to k. The worst case would be when the array x was in
' ascending order since then x(i) would have to be inserted
' for each i. Similarly, in the case the array x is in
' descending order, after m inserts, no more inserts will
' be done. For the order of array x 'random', once a
' relatively large fraction of the m largest are in the
' heap, additional inserts become relatively rare.
'
' This routine is to be 'polymorphic', that is, to work for
' essentially any user defined class my_class1 where
'
' Dim m, n As Int32
' Dim x( n ) As my_class1
' Dim y( m ) As my_class1
'
' This routine can build an ascending heap, as discussed
' above, or a descending heap. The only difference is how
' the comparisons are made in the class used for the
' interface.
'
' The interface IComparer is used. If the usual class
' Comparer is used for this interface, then this function
' builds an ascending heap, that is, where upon return
'
' y( 1 ) <= y( j ),
'
' for j = 2, 3, ..., m.
Function obj_heap_insert( _
x As Object, _
y() As Object, _
ByRef k As Int32, _
m As Int32, _
compare As IComparer) As Int32
Dim routine_name As String = "obj_heap_insert"
Dim error_code As Int32
Dim return_code As Int32 = 0
' Dim result_code As Int32
Dim message_tag As Int32
Dim i_father As Int32
Dim i_child0 As Int32
Dim i_child1 As Int32
Dim i_child2 As Int32
Dim i_2 As Int32 = 2
Try
error_code = 1001
message_tag = 1001
If console_msg_level >= console_routine_messages2 Then _
Console.WriteLine( routine_name & " " & message_tag & _
": Started ..." )
error_code = 1002
If m <= 0 Then
return_code = 1001
Goto out
End If
If k < 0 Then
return_code = 1002
Goto out
End If
...
> Toit is a modern high-level language designed specifically for microcontrollers
> Toit is optimised for live reloading on your microcontroller. Your code runs incrementally as you write it and you get instant feedback. Push changes over your local WiFi in two seconds and reserve your USB cable for charging your phone. You iterate quickly, learn fast, and build better things.
Any comparison based sorting algo can be made stable. Consider position as a tie breaker.
Most can be done in place with some effort.
Then you need to worry not about asymptotics, but the constant factors. Quicksort has significantly lower operation count than heap sort, even though both are O(nlog n). For small numbers bubble sort is quicker than both (and many good sorts leverage this via hybrid methods). Caches add another massive game changing performance dial to fiddle with.
Taking stock at this level, ignoring that many of the non-green field he chose can be made green, misses important nuance.
83 comments
[ 2.2 ms ] story [ 1042 ms ] threadNot the prettiest code, but it's in the examples directory at https://github.com/toitware/toit-png-display if anyone cares.
Like it probably doesn't matter if you're sorting 10k entries, but when you're sorting several gigabytes it really does.
The actual implementation in Toit does depth first, so eg. the leftmost 8,8->16 merge is done as soon as the 8-element ranges are ready.
Collecting those nine elements looks terrible for locality.
Funnelsort is a cache oblivious variant of merge sort which is provably cache optimal in some sense. I haven't tried implementing it.
https://en.wikipedia.org/wiki/Introsort#Implementations
And heapsort has terrible cache behaviour.
Eventually I realized I was running out of desk space, so I started merging little stacks of around equal size.
So the base case wasn’t 1 element, but that’s conventional for actual implementations. And the splitting wasn’t quite recursive I guess. But partial credit at least.
This cost model is an important reason to merge bottom up, from sorted subsequences, without arbitrary splitting that can add work but not reduce it.
I think back on it with a certain amount of nostalgia now, but it was a stupid way to do operations, even at the time, They had invested big in computers in the 70's and were still maintaining the same tech stack in the early 00's when I worked there.
I vaguely recall JSC actually having a literal tree sort at one point to deal with this.
This is in a JS engine, where by design all code is untrusted.
If you are a JS engine, then arbitrary code execution, failure to terminate, or crashing is never an acceptable outcome, regardless of how bad the code is, because again, you're dealing with untrusted input. The assumption for a JS engine is necessarily that all code is malicious.
But the JS engine does not protect against the page containing JS code that loops forever. How would it even do that?
Edit: Perhaps some misunderstanding: V8 "just used Quicksort", but it never used the qsort function from the C library. That would not have worked with garbage collection, since you can have a garbage collection in the middle of sorting, which could move the array.
But the point is that the general quicksort algorithm does a bunch of unsafe memory accesses if the comparator is unstable (either directly or by modification of the sorted data). As demonstrated by every qsort implementation going wrong in unsafe ways in such a scenario.
Now maybe you used a version of qsort that actually made sure it wasn’t going out of bounds and what not and did … something? When that occurred, and saying what that something was would be a reasonable answer.
As for qsort() not being an option due to gc, that’s only a problem due to v8’s gc - JSC for instance could just use qsort or what not if it was sure the sort was consistent.
Timsort is from 2002. Not sure where this comes from. Perhaps it wasn't as popular or widely known in 2008 as it is now, but I actually learned about it at about that time. See also:
https://mail.python.org/pipermail/python-dev/2002-July/02683...
(edit: timsort was introduced to Java in 2009, per https://bugs.openjdk.org/browse/JDK-6804124, and knowledge of it would probably have spread much further from that point, so maybe that's the source of confusion?)
(With that said, Timsort must be faster in practice than this kind of retrofitted unstable sort. I’m curious how large the difference is.)
But yeah, I don't usually need stability either.
Let's say you're sorting a bunch a unlabelled images. You can sort them by number of pixels, that's pretty clear but will likely have clashes.
You could then sort by either width of height next, but the choice is pretty arbitrary. It's not obvious why a 100x10 pixel image should come before or after a 10x100 pixel image. But it's not very weird to pick one either.
Next you could sort on properties of the first pixel. But those are multidimensional. Sorting by the most red first, for example, would be weird.
You could still create an ordering if you need the consistency, but it wouldn't mean anything.
If you don't sort by them, you can get images that are different in ways that aren't sorted. Stability (well, instability) becomes detectable.
If you have to use an unstable sorting algorithm you'll be stuck choosing between images jumping around or being in a certain spot because the 34th pixel on the 56th line is slightly more greenish than in the image before it. It can depend on your use case which of those is least desirable.
Having a stable sort would give you another option.
Asking because you're actually describing a problem I have with a data set :D
The easiest way to transform an unstable sort into a stable sort is probably mapping input from T -> (Index, T) and including the index as a sort key.
It is a new stable sorting algorithm that is a hybrid of quicksort and mergesort which is much faster for random data, while still taking full advantage of pre-existing order or inputs with many duplicates. On an Apple M1 in Rust the latest version is ~4.5x faster than the stdlib slice::sort for sorting 2^25 random integers while using 4 times less extra memory. It is 11.5x faster if you happen to sort only 4096 distinct integers with many duplicates. Note that the algorithm is purely comparison based and does not contain special type-dependent SIMD stuff.
I have a short preliminary talk on glidesort here: https://www.youtube.com/watch?v=2y3IK1l6PI4.
Perhaps the V8 people will be interested in it as well.
Is Glidesort1024 still stable?
I thought that sorting algorithms were at a culminating point, but it appears this is not the case at all.
(Here's where I hope I'm asking a dumb question and you already have, but I haven't been able to find it.)
I would assume that they're faster, especially if using SIMD.
A number n is bit reversed if it is written was written in binary (base 2) and then the bits were written in reverse order.
Last time I looked at Shell sort, when sorting n records on keys in bit reversed order, the iterations of Shell sort did nothing until the last iteration at which time Shell sort was just bubble sort or some such and, whatever, ran in time O(n^2) where the O() is some obscure but now common notation. The article claims something smaller than O(n^2). Okay, but to get something smaller, have to tweak what used to be a standard version of Shell sort.
For another point, the article wants a stable sort -- if two records (the data being sorted) A and B have equal keys and before the sort record A is before record B, then after the sort record A will still be before record B. But, if want a stable sort, then for one approach, before the sort, number the records and use these numbers as part of the keys. Right this extra step runs in time O(n) and uses extra temporary, working storage proportional to n. For current computing, is this extra storage a meaningful issue?
My favorite is heap sort, guaranteed O(n log(n)) average case and worst case, meets the Gleason bound and, thus, is the fastest possible sort based on comparing pairs of keys (in one of volumes of D. Knuth, The Art of Computer Programming).
You mentioned simple: The logic of the heap data structure and its corresponding code seem to be relatively simple.
Of course, radix sort does not work by "comparing pairs of keys", may be regarded as O(n), and, check this, may also be stable. Of course, radix sort was the algorithm of the IBM punched card sorting machine so maybe goes back to before 1900 and, thus, is likely the oldest of the common sorting algorithms.
Below (in a separate post) is code for
which is an (ascending integer) heap sort routine.Right, this code is for only ascending, integers, and arrays and, thus, is far from the practice of generic code, e.g., as in
https://en.wikipedia.org/wiki/Generic_programming
The advantages of generic code my work doesn't really need. Once I wrote some generic code, and that experience was enough!
The code is in Microsoft's Visual Basic .NET.
Why Visual Basic .NET?
I have written some C code. There are claims that the programming language C has idiosyncratic syntax. Whatever it has, I don't like its syntax. I.e., supposedly
is legal -- increase j and k by 1, add the results, assign the result to i, and then increase j and k by 1 again -- but when I tested this on two different C compilers I got different results. If the compilers can't agree on the syntax, I don't want to try to understand it! Besides, C is supposed to be really simple, close to assembly language, and highly portable, and ambiguity I observed for conflicts with those attributes! Besides, that syntax gets the grand prize for not just idiosyncratic but obscure, ugly, outrageous, etc.!Maybe C and C++ are essential for Windows internals and for Windows applications that make direct use of the System32 API, but I've never written such code since my background is applied math software.
Thus, also I don't like the related syntax of C++ or C#.
The syntax of Visual Basic .NET (VB) is more traditional, more like the original Basic, then Fortran, Algol, Pascal, and PL/I (maybe my favorite).
Thus, VB is relatively easy to teach, learn, read, and write, and these attributes might be considered important in a large project!
Whatever the syntax of VB is, there are claims that VB and C# have equivalent semantics and differ only in syntactic sugar. I.e., supposedly there is a source code translator program than can translate code in either of VB or C# to the other.
So, for my project, code to run on Windows, I am writing in VB instead of C#.
Also below (in a separate post) is code
Function obj_heap_insert
Here I use the heap data structure, the main idea in heap sort, to maintain a priority queue. So, with this code can look at 20 million objects one at a time and end up with, e.g., the 20 largest. Uh, how else to do that???!!!
Right, this code starts to be a little big generic.
Right, operating on the heap data structure can hurt possibly desired main memory and cache memory locality of reference, but there is at least one modification of modifying operations on a heap that speed up what otherwise might be the case of a heap large enough to need virtual memory.
All this code appears to run correctly. I have later versions modified, longer, less easy to read, to use an error handling technique I cooked up -- really simple, I wouldn't recommend for larg...
If I had to do it again, I would make it stable now.
https://github.com/dart-lang/sdk/issues/433#issuecomment-108...
I'd be perfectly fine with just having to call StableSort vs Sort once in blue moon when I need it
https://toitlang.org/
> Toit is a modern high-level language designed specifically for microcontrollers
> Toit is optimised for live reloading on your microcontroller. Your code runs incrementally as you write it and you get instant feedback. Push changes over your local WiFi in two seconds and reserve your USB cable for charging your phone. You iterate quickly, learn fast, and build better things.
Most can be done in place with some effort.
Then you need to worry not about asymptotics, but the constant factors. Quicksort has significantly lower operation count than heap sort, even though both are O(nlog n). For small numbers bubble sort is quicker than both (and many good sorts leverage this via hybrid methods). Caches add another massive game changing performance dial to fiddle with.
Taking stock at this level, ignoring that many of the non-green field he chose can be made green, misses important nuance.