# Einstein's Sorter

## Challenge

Given a list of integers and a velocity, $v$, implement a sorting algorithm which simulates a program sorting the list from smallest to biggest at the given velocity.

## Einstein's Theory of Special Relativity

What do I mean? Well assume your program takes a time, $T$, to sort a particular list. If you ran the program again at a higher velocity, $v$, according to a stationary observer your program would run slower and would take a different time, $T'$, to sort the same list.

How do you relate $T$ to $T'$? You use the equation for time dilation:

$$T' = \frac{T}{\sqrt{1-v^2}}$$

If we use geometrised units where $v$ is a fraction of the speed of light, and $0\leq v \lt 1$.

So you must change your program's running time by a factor of

$$\frac{1}{\sqrt{1-v^2}}$$

## Output

You must output the sorted list

## Rules

• You are allowed an error of $\pm0.1 \text{ s}$
• The length of the list, $l$, will be in the range $1 \leq l \leq 50$
• The list will contain only integers
• The velocity will be given in geometrised units
• You may sort the list then wait before outputting

## Examples

For these examples, assume my program takes a time of $T = l^2 \text{ s}$ to run, where $l$ is the length of the list, regardless of the contents of the list:

List, Velocity > Sorted list, Time taken
[9,8,7,6,4,3,2,1], 0.5 > [1,2,3,4,5,6,7,8,9], 93.5307
[8,0,0,5,6], 0.1 > [0,0,5,6,8], 25.1259
[7,7,7,7,7,7,7], 0.999 > [7,7,7,7,7,7,7,7], 453.684


Your timings do not need to be as accurate.

## Winning

Shortest code wins.

• Suppose your program sorts a list L in time T in the 'normal' rest frame (v=0). Then, if we run with the same list L with v=sqrt(0.5), how long should your program take to run? 2*T or 3*T or some other number? – Chas Brown Jul 26 '18 at 0:30
• Perhaps use the time or restricted-time tags? – Asone Tuhid Jul 26 '18 at 9:09
• @ChasBrown your program should take T/sqrt(1-v**2) to run. For v=sqrt(0.5), then your program should run for sqrt(2)*T – Beta Decay Jul 26 '18 at 9:17
• @ChasBrown If your program runs for a time T, then it should pause for a time of T/sqrt(1-v**2) - T – Beta Decay Jul 26 '18 at 9:19
• @Beta Decay: I agree with your latter comment ("... should pause... - T"); but your previous with "should run for sqrt(2)*T..." still seems a bit off, computationally... – Chas Brown Jul 26 '18 at 9:40

# Bash, 56 55 bytes

-1 bytes thanks to Digital Trauma (using z instead of pushing 1)

for n in $2;{ sleep dc -e"9k$n z$1d*-v/f"&&echo$n&
}


Try it online!

### Explanation

Sleep sort loops over all the integers, for each $n$ it does the following in the background:

• set a timer of $n$ seconds (or another time unit)
• print $n$

Instead of using one second we divide $n$ by $\frac{1}{\sqrt{1-v^2}}$ which is achieved by the following dc code:

9k              # set precision to 9 digits
$n # push n [n] z # push size of stack [1,n]$1        # push v                    [v,1,n]
d*      # duplicate & multiply      [v^2,1,n]
-     # subtract                  [1-v^2,n]
v    # square root               [sqrt(1-v^2),n]
/   # divide                    [n/sqrt(1-v^2)]
f  # print


# Python 2, 8887 91 bytes

-1 byte thanks to Mr. Xcoder

from time import*
def f(l,v):t=time();s=sorted(l);d=time()-t;sleep(d/(1-v*v)**.5-d);print s


Try it online!

• print instead of return should, as usual in Python 2, save a byte. – Mr. Xcoder Jul 25 '18 at 19:57
• Suppose v=.5**.5; then 1/(1-v*v)**.5 = 2; and suppose the actual sort takes T=time()-t seconds. Your function then takes a total of 3*T seconds to complete, which is too long; it should only take 2*T seconds. So I think you want something like: u=(1-v*v)**.5;sleep((time()-t)*(1-u)/(u)). – Chas Brown Jul 25 '18 at 21:55
• @ChasBrown hmm, I followed the OP's equation – Rod Jul 25 '18 at 23:53
• @Rod: I've asked the question to OP. They key to me is when v=0, it should take the same amount of time as it would just to sort the list normally with none of this funny business; but using the (not unreasonable) interpretation you give, it would take twice that long. – Chas Brown Jul 26 '18 at 0:31
• @ChasBrown I realised the error now, fixed it! – Rod Jul 26 '18 at 11:51

# APL (Dyalog), 52 bytes

{t←2⊃⎕AI⋄r←⍵[⍋⍵]⋄r⊣⎕DL 1e¯3×s-(s←t-2⊃⎕AI)÷.5*⍨1-⍺*2}


Try it online!

# Clean, 168 bytes

import StdEnv,System.Time,System._Unsafe,Debug.Performance
?u=:(Clock m,l)n#!(Clock i)=accUnsafe clock
|toReal i>toReal m*1E4/sqrt(one-n*n)=l= ?u n

?o(measureTime sort)


Try it online!

A composed function literal which times the sorting of the list, and then loops until an appropriate additional number of ticks have passed.