Timeline for How many comparative sorting algorithms are there?
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 1 at 14:17 | history | edited | sbh | CC BY-SA 4.0 |
added 23 characters in body; edited tags
|
| Feb 1 at 8:38 | comment | added | greybeard | I can see that there need to be $n$ leaves - input nodes? But what is the significance of the root? Does not every input value need to reach one output node? You may be reinventing sorting networks from 2-sorters. | |
| Feb 1 at 7:12 | comment | added | sbh | $\lambda$ is not necessarily a permutation of $1, 2, ..., n$, as the input is not limited to that. It's okay anyway, as we can make this assumption without causing a change to the answer. | |
| Feb 1 at 7:07 | comment | added | D.W.♦ | Thank you. Please check my edit to see whether it accurately reflects your intent. | |
| Feb 1 at 7:07 | history | edited | D.W.♦ | CC BY-SA 4.0 |
Clarify question based on comments.
|
| Feb 1 at 6:49 | comment | added | sbh | $\lambda$ denotes a single leaf, and I'm saying that these 3 conditions must hold for all the leafs $\lambda$. A comparative sorting algorithm takes $n$ and an array of size $n$, and I'm saying that all the leafs $\lambda$ are a permutation of that (that also implies that they are the permutation of themselves), and all the permutations of the input array must be covered by the algorithm, that the condition $i)$ requires that. | |
| Jan 31 at 19:35 | history | edited | sbh | CC BY-SA 4.0 |
added 7 characters in body
|
| Jan 31 at 19:27 | history | asked | sbh | CC BY-SA 4.0 |