• Subject: Re: Length-unaware sorting algorithm
• From: "Soni L." <fakedme@...>
• Date: Thu, 25 Aug 2016 22:54:02 -0300

```

On 25/08/16 10:45 PM, Sean Conner wrote:
```
```It was thus said that the Great Soni L. once stated:
```
```If you wanna try this as a challenge:
http://codegolf.stackexchange.com/questions/91143/sort-an-array-without-knowing-its-length#

(And no, ipairs() and stuff is not allowed. ipairs() looks for the first
nil and treats that as the array boundary, which in this case counts as
an explicit length calculation.)
```
```   You're moving the goal posts YET AGAIN!  I quote from your question on
Code Challenge:

The end of the array is a sequence of some value we'll call
\$PLACEHOLDER repeated for the same length as the array itself. You
```
```
```
I meant you can use the fact that you have \$ARRAY_LEN valid slots that all contain \$PLACEHOLDER after \$ARRAY_LEN to your advantage.
```
```
E.g. an array of length 2 isn't just {1, 2, nil}, it's {1, 2, nil, nil}, and slots beyond those are invalid (e.g. t[5] is invalid, t[4] is valid and gives you nil, t[0] is invalid).
```
I thought that part was clear...

```
```
In the case of Lua, \$PLACEHOLDER is nil.

So, can we use nil, or not?  What is the difference between ipairs()
stopping on a nil, and our code stopping on a nil?  Just how are we to
detemine the end of input?

Soni, if you are *really* interested in the answer, I implore you to read
Chapter 5 of _The Art of Computer Programming_ by Donald Knuth.  It's a
quick read [1] that covers everything there pretty much is to know about
sorting and then some.  You should be able to find a copy via a library
(it's a bit pricy).

-spc (More specifically, Chapter 5, section 2, "Internal Sorting".  That's
```