# Lossy Sorting (Implement Dropsort)

Dropsort, designed by David Morgan-Mar, is an example of a linear-time "sorting algorithm" that produces a list that is, in fact, sorted, but contains only some of the original elements. Any element that is not at least as large as the maximum of the elements preceding it is simply removed from the list and discarded.

In this task, you will be given a list of integers as input (STDIN or function argument, you are required to support at least the range of 8-bit signed integers.) Your task is to dropsort them and then output the remaining elements in order.

You may assume that the list is non-empty.

This is code golf, so the shortest program wins.

Test Cases

Input             Output
1 2 5 4 3 7       1 2 5 7
10 -1 12          10 12
-7 -8 -5 0 -1 1   -7 -5 0 1
9 8 7 6 5         9
10 13 17 21       10 13 17 21
10 10 10 9 10     10 10 10 10


var QUESTION_ID=61808,OVERRIDE_USER=39022;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>

• Is the check highest < current? Or highest <= current? Oct 26 '15 at 13:20
• Keep the current element if highest (so far)<=current. Oct 26 '15 at 13:21
• Can we assume that there will be at least one element in the list? Oct 26 '15 at 20:44
• @ThomasKwa: Yes. Oct 26 '15 at 20:49
• Dropsorts improved efficiency could save a company a lot of money if utilized in the payroll system. Oct 26 '15 at 21:06

# APL, 9 bytes

⊢(/⍨)⊢=⌈\


This is a monadic function train with diagram:

┌─┼───┐
⊢ ⍨ ┌─┼─┐
┌─┘ ⊢ = \
/     ┌─┘
⌈


The non-train version is

{⍵/⍨⍵=⌈\⍵}


This basically checks if each element is equal to the running maximum.

Note that Martin Büttner's J solution is the same length as this and was posted first.

• Bonus points because it looks cute. Oct 26 '15 at 18:02
• Code looks like a disgruntled dude shooting at a cat flap Oct 27 '15 at 5:42
• I don't know much about byte counting and what encoding is intended to be used, but according to mothereff.in/byte-counter and meta.codegolf.stackexchange.com/questions/4944/… this is 17 bytes, and bytesizematters.com it's 13.
– DLeh
Oct 28 '15 at 15:43
• @DLeh That's in UTF-8. APL has its own legacy encoding that is 1 byte per APL character, from before unicode existed. Oct 29 '15 at 16:52
• @DLeh bytesizematters uses a made up algorithm to count the bytes, which does not (and cannot) correspond to an actual encoding. Feb 19 '16 at 18:00

# J, 10 9 bytes

#~(=>./\)


Working version of my CJam idea (in fewer bytes). E.g.:

   f =: #~(=>./\)
f 10 10 10 9 10
10 10 10 10
f 1 2 5 4 3 7
1 2 5 7


## Explanation

First, we get the maximum of each prefix, with:

    >./\


(Here, >. is the maximum operator, / folds that operator onto a list, and \ gets all the prefixes of the input.)

Then we compare the initial list with those maxima for equality:

  (=>./\)


And finally, we select all elements where this list of boolean results gave a 1:

#~(=>./\)


foldr(\x l->x:filter(x<)l)[]


An anonymous function. Call it like

foldr(\x l->x:filter(x<)l)[] [-7, -8, -5, 0, -1, 1]
[-7,-5,0,1]


Equivalent to the recursion

f[]=[]
f(x:l)=x:filter(x<)(f l)


Translated iteratively, we iterate over the elements, and for each one we see, we remove the ones smaller than it from the remainder of the list that we're iterating over. Thanks to Antisthenes for a byte saved with (x<).

• Why not curry the lambda? Should save a few characters... Oct 29 '15 at 12:47
• @MathematicalOrchid If you mean foldr(\x->(x:).filter(>=x))[], that turns out to be the same length.
– xnor
Oct 29 '15 at 22:55
• Ah. I just saw the filter at the end and thought "hey, you can curry that!" Didn't occur to me that the x: forces you to add the dot operator. Oh well... Oct 30 '15 at 8:10
• it's O(n^2) though. lots of unneeded comparisons. ;-( Mar 27 '16 at 22:27
• Why not change (>=x) to (x<)? It will save 1 byte Jun 16 '17 at 20:02

# JavaScript (ES6), 29

Abusing of the standard type conversion in javascript, array to number:

• array of just 1 number => that number
• any other array => NaN

d=l=>l.filter(v=>l>v?0:[l=v])

// TEST
console.log=x=>O.innerHTML+=x+'\n'

;[
[[1,2,5,4,3,7], [1,2,5,7]]
, [[10,-1,12], [10,12]]
, [[-7,-8,-5,0,-1,1], [-7,-5,0,1]]
, [[9,8,7,6,5], [9]]
, [[10,13,17,21], [10,13,17,21]]
, [[10,10,10,9,10], [10,10,10,10]]
].forEach(t=>( i=t[0],r=d(i),x=t[1],
console.log('Test '+i+' -> '+r+(r+''==x+''?' OK':' Fail (expected '+x+')')))
)
<pre id=O></pre>

• Wow. I thought 38 bytes was approximately the best possible; apparently I was very wrong. +1 Oct 26 '15 at 15:45
• Table driven tests. Nice! Oct 27 '15 at 5:43

# Brachylog, 5 bytes

⊇ᶠ↔ᵒt


Try it online!

# Jelly, 5 bytes

ŒPUÞṪ


Try it online!

## Explanation

⊇ᶠ↔ᵒt    ŒPUÞṪ
⊇ᶠ       ŒP       On all subsequences of {the input}
ᵒ        Þ     sort by
↔        U      their reverse
t        Ṫ    then take the last element (i.e. the maximum as given by the sort)


This is a rare situation: I get to use an algorithm which (as far as I could tell with a quick skim) nobody is using so far, and it somehow ends up the same length in two very different golfing languages with very different syntax and builtin sets, with a 1-to-1 correspondence between the programs (the commands are even in the same order!). So it seemed to make more sense to combine them – in a way, these are the same program, and I wrote it in both languages to see which was shorter – than to submit them separately.

The basic idea here is that the dropsort of a list is its subsequence with the lexicographically maximum reverse. Oddly, neither Brachylog nor Jelly has a builtin to find the maximum by a particular function (Jelly has a builtin to return all the maxima by a particular function, but that'd return a singleton list containing the result rather than the result itself, and also isn't even shorter than doing it this way). So instead, we generate all possible subsequences, sort by reverse, take the last.

The reason why "lexicographically maximum reverse" works is that the chosen output must end (thus its reverse must start) with the highest number in the input list (it's easy to see that the dropsort output will always end with that), and thus can't contain anything after that (because taking subsequences preserves order). Repeat inductively and we end up with the definition of dropsort.

# Python 2, 49

f=lambda a:a and f(a[:-1])+a[-1:]*(a[-1]==max(a))

• This is amazing. Oct 26 '15 at 17:46
• @ThomasKwa The problem is how do you stop the recursive calls. You need the empty case even if the input excludes that case. Oct 27 '15 at 12:39
• problem with that is that it is not linear because of max(a) Oct 28 '15 at 20:31
• @njzk2 The challenge does not require the implementations to run in linear time. Oct 28 '15 at 20:50
• @njzk2 Nice codes finish last! Oct 28 '15 at 21:06

# Octave, 27 19 bytes

@(a)a(cummax(a)==a)


# Pyth, 12 bytes

eMfqeTeST._Q


Verify all test cases at once.

### How it works

         ._Q  Compute all prefixes of the input.
f           Filter; for each T in the prefixes:
eT          Retrieve the last element of T.
eST       Sort T and retrieve its last element.
q            Check for equality.
Keep T if q returned True.
eM            Select the last element of each kept T.


# Mathematica, 26 Bytes

DeleteDuplicates[#,#>#2&]&

• I don't know Mathematica, but something that calls DeleteDuplicates doesn't look like it would return {10, 10, 10, 10} for input {10, 10, 10, 9, 10} Oct 27 '15 at 15:49
• @Dennis: It does, I tested it. The trick is that I pass "is greater than" as "equivalence" test. Yes, it's a misuse of that function, but it works, and code golf is not exactly about best programming practices anyway. Oct 27 '15 at 19:02
• OK, in spite of what the name suggests, DeleteDuplicates with two arguments seems to be a simple filter. Oct 27 '15 at 19:19

# R, 29 26 bytes

function(x)x[x>=cummax(x)]


This creates a function object that accepts a vector x and returns x after removing all elements not at least as large as the cumulative maximum of x.

Saved 3 bytes thanks to flodel!

• The function form would be shorter. Oct 26 '15 at 23:10
• @flodel You're absolutely right. Thanks! Oct 26 '15 at 23:19

# K, 11 bytes

{x@&~x<|\x}


In action:

  f: {x@&~x<|\x}
f'(1 2 5 4 3 7
10 -1 12
-7 -8 -5 0 -1 1
9 8 7 6 5
10 13 17 21
10 10 10 9 10)

(1 2 5 7
10 12
-7 -5 0 1
,9
10 13 17 21
10 10 10 10)

• {x@&~<':x} is a byte shorter. Oct 26 '15 at 16:04
• @kirbyfan64sos: Using eachprior does not produce the correct result. Consider the input case 3 4 2 2 5. Oct 26 '15 at 17:42
• Ah, I see. A fix would be {x@&~<':x}/, but that's the same length. Oct 26 '15 at 19:59

# Java, 82 bytes

void f(int[]a){int m=a[0];for(int n:a){System.out.print(m>n?"":n+" ");m=n>m?n:m;}}


Here's a simple output loop. It just keeps the max in m and compares each element.

• You can shorten it by using a lambda: a->{int m=a[0]... Oct 27 '15 at 17:14
• Yea, you usually can. I don't lambda-ize java golfs, though. Oct 27 '15 at 17:57

## Perl, 33 bytes

32 bytes code + -p

$p=$_;s/\S+ ?/$&>=$p&&($p=$&)/ge


If additional spaces are acceptable in the output, can be 31 bytes by removing and ?. Accepts a string (or number of newline separated) strings via STDIN:

perl -pe'$p=$_;s/\S+ ?/$&>=$p&&($p=$&)/ge' <<< '-7 -8 -5 0 -1 1'
-7 -5 0 1

perl -pe'$p=$_;s/\S+ ?/$&>=$p&&($p=$&)/ge' <<< '10 10 10 9 10'
10 10 10 10


# Python 3, 67

Pretty brute force. Changed it to a function, because I missed that it was a valid answer.

def f(i):
s=[i[0]]
for n in i[1:]:
if s[-1]<=n:s+=[n]
return s


Ungolfed version:

input_numbers = input().split()
sorted_numbers = []
previous_number = int(input_numbers[0])
for number in map(int, input_numbers):
if previous_number <= number:
sorted_numbers.append(number)
previous_number = number
print(sorted_numbers)

• 62 bytes Aug 14 '19 at 20:49

Saved 1 byte thanks to JArkinstall.

f(x:y:s)|x>y=f$x:s|1>0=x:f(y:s) f s=s  • You can replace one of your sets of parentheses with a $ to cut down by one whole byte! f(x:y:s)|x>y=f$x:s|1>0=x:f(y:s);f s=s (Semi-colon used because comments don't allow newlines) – Jake Oct 27 '15 at 1:14 # C# - 6864 or 132127 Characters int[]f(int[]b){return b.Where((v,i)=>i<1||b[i-1]<=v).ToArray();}  Where in this case is iterating through the list, and for each element v at index i in the list, evaluates the boolean expression. If the expression evaluates to true, then the item is added to the result. The only real trick to the boolean expression is that C# short circuits or evaluation as soon as a condition evaluates to true. This prevents the IndexOutOfRangeException exception, and keeps the first element in the list. If the input and output have to be strings (I couldn't tell for sure, so I'll leave it to the OP and the rest of you to decide.) string t(string b){var c=b.Split(' ').Select(d=>int.Parse(d)).ToList();return String.Join(" ",c.Where((v,i)=>i<1||c[i-1]<=v));}  Decompressing that a bit gives: string t(string b) { var c=b.Split(' ').Select(d=>int.Parse(d)).ToList(); return String.Join(" ",c.Where((v, i)=>i<1||c[i-1]<=v)); }  In this case the second line of the function is using the exact same logic as above. The Select grabs the elements of the list and converts them to int. The call to ToList1 forces the select to be evaluated, and turns the var into a List<int> at compile time, so that the Where is operating on a collection of integers. Try it on C# Pad Thanks to VisualMelon for helping trim 4 bytes and 5 bytes respectively. :) 1 tutu list? • If I miscounted, or if my explanation needs some explaining, please let me know. :) – theB Oct 27 '15 at 2:58 • Nice work - you can save a few bytes by using some common tricks - you don't need the spaces after the array declarations int[]f(int[]b) is fine, and you can use i<1 rather than i==0 to shorten that check a bit. For the string version, you can also drop the brackets around a single-argument in a lambda (e.g. (d)=>int.Parse(d) can be d=>int.Parse(d). I also only count 67 bytes, not 68, in your orignal ;) Oct 27 '15 at 9:13 • @VisualMelon - Thanks! I figured that any miscounting would end up making the total bigger. ;) – theB Oct 27 '15 at 9:28 # CJam, 15 bytes q~{_2$<{;}&}*]p


Try it online in the CJam interpreter.

### How it works

q~               Read an evaluate all input.
{        }*    Reduce; push the first element; or each remaining element:
_2$Copy the topmost and second topmost element from the stack. < Check if the topmost is smaller than the second topmost. {;}& If it is, remove it from the stack. ] Wrap the stack i an array. p Print.  # PowerShell, 32 bytes $args|?{$e-eq$p-or$_-ge$p;$p=$_}


Try it online!

Less golfed:

$args|?{$empty -eq $previous -or$_ -ge $previous$previous = $_ }  # C: 73 bytes int i,j;i=j=INT_MIN;while(scanf("%d",&j)!=EOF)if(j>=i)printf("%d",j),i=j;  or # C: 49 bytes (If customs header made for codegolf competitions is allowed) I z,y;z=y=INT_MIN;w(s(D,&y)!=E)i(y>z)p(D,y),z=y;}  Still can't beat CJam, but at least this allow to beat few other languages. • Sorry, the custom header isn't allowed; it would count as a different language. Oct 26 '15 at 17:07 • The primary problem with your custom headers is that you published them after this competition started. Oct 26 '15 at 19:31 • Sure I understand, but then I cannot use it neither in future competitions? Oct 27 '15 at 9:24 • @DarioOO You can, but you'd be required to include the import statement towards your byte count. Mar 15 '16 at 14:14 • Or just call it a new language. Mar 22 '16 at 4:07 ## Burlesque, 13 bytes 11 byte solution that passes test-cases: -.2CO:so)[~  Explanation: -. -- prepend head of list to list 2CO -- n-grams (sliding window) of size 2 :so -- filter sorted lists )[~ -- map last  However, this version only works by using the fact, that no two smaller numbers are in between two numbers. Otherwise use the version below (which is 13B): Older versions: J-]{cm-1.>}LO  Try online here. Explanation: J -- duplicate -] -- head { cm -- compare (returning -1,0 or 1) -1.> -- greater than -1 }LO -- Loop  If you'd drop equal numbers as well you could go with just .> instead of using cm. Also, if lists only contain positive numbers you can use either 0 or -1 instead of J-]. • Yeah, but then I can't hyperlink it :). Oct 26 '15 at 16:44 • fixed. I'll just add a "try online here" line. Oct 26 '15 at 16:46 ## Minkolang 0.9, 18 bytes ndN(nd1R2&dN$I$).  Try it here. ### Explanation ndN Take first integer from input ($I$). Repeat until the input is empty and then stop. nd1R Is the next integer less than the previous one? 2&dN If not (i.e., it's greater than or equal to), print it.  # NARS2000 APL, 13 bytes NARS2000 is a free APL interpreter for Windows; it includes multiset features accessed with the ⍦ operator. (+⍦∩⌈\)  This is a monadic fork that takes the multiset intersection (⍦∩) of the input (+)* and the list of running maximums (⌈\). Since ⍦ is not a standard APL character in the one-byte APL legacy encodings, we must use UTF-8, making the ⍦∩⌈ characters three bytes each. I chose + instead of ⊢ to save two bytes. NARS2000 supports forks, which can be built into trains without parentheses, but unlike Dyalog it doesn't allow assignment to a function without wrapping the function in parentheses. *+ is technically complex conjugate, but the input is real. • So, why doesn't codegolf.stackexchange.com/questions/61808/… apply here too? – cat Mar 21 '16 at 20:02 • NARS2000 can't use the legacy APL encodings--and even before the rule that encodings must be the ones actually used by interpreters, this couldn't be 7 bytes because psi isn't part of any legacy APL encoding. Mar 21 '16 at 21:48 # ><> with -v flag, 36 31 + 2 = 33 bytes :&\o " "&n:~& < ~ >l?!;:&:&(?!^  Input the list on the stack with -v so that the first element of the list is at the top of the stack. It will print the dropsorted list with a trailing space. Test run : $ for input in "1 2 5 4 3 7" "10 -1 12" "-7 -8 -5 0 -1 1" "9 8 7 6 5" "10 13 17 21" "10 10 10 9 10"; do echo $input '-> '$(python fish.py dropsort.fsh -v $(echo$input | tac -s ' ')); done

1 2 5 4 3 7 ->  1 2 5 7

10 -1 12 ->  10 12

-7 -8 -5 0 -1 1 ->  -7 -5 0 1

9 8 7 6 5 ->  9

10 13 17 21 ->  10 13 17 21

10 10 10 9 10 ->  10 10 10 10


Edit : saved 5 bytes thanks to Fongoid

• You can save 5 bytes by refactoring line 1 as :&\o" "&n:~& < and line 2 as ~ >l?!;:&:&(?!^ Oct 27 '15 at 21:42
• @Fongoid thanks, updated ! Oct 28 '15 at 10:37

# Python, 10299 94 + 5 6 non-file-final newlines = 107105 100 bytes

(I used tabs for indentation)

def d(l):
j=b=0;m=l[j];r=[]
for i in l:
(m,b)=[(m,0),(i,1)][i>=m]
if b>0:r+=[i]
j+=1
l[:]=r


Not the best out there, but this is my first shot at code golf. Couldn't figure out a way to sort the list inline without running into removal-related bugs, so I moved the ordered elements to a temporary list.

EDIT: list.append() is shorter than doing it the ugly way

r+=[i] was shorter than list.append(); thanks njzk2!

• r+=[i] is shorted than r.append Oct 28 '15 at 20:44
• I tried doing that before, but got an error because I didn't realize you have to do it with brackets. Thanks! Oct 28 '15 at 20:57

# Scala: 232126 120 bytes

def f(x:Int*)=(Seq[Int]()/:x)((r,y)=>r.headOption.filter(y>=).map(_=>y+:r).getOrElse(if(r.isEmpty) y+:r else r)).reverse

• Adding an "extension method" for List[Int] does not meet requirements, you should get the input via STDIN or as an argument. Plus, it bloats your answer... Why not simply have def dropSort(s:Seq[Int]):Seq[Int]? Oct 27 '15 at 15:47
• I thought it would be fancy, but you're right, way too much bytes... Oct 27 '15 at 19:07
• Very nice improvement using fold! You can still shave off some spaces and also you can use y>= rather than _<=y which yields a compile warning without a proper import, but also demonstrates how awesome Scala is (oh, and shaves off another character). Oct 28 '15 at 22:33
• Thx for the tipp! Oct 29 '15 at 7:07

# Scala, 54 bytes

def f(x:Int*)=(x:\Seq[Int]())((y,r)=>y+:r.filter(y<=))


Ungolfed:

def dropSort(xs: Seq[Int]): Seq[Int] =
xs.foldRight(Seq.empty[Int]) { (x, result) =>
x +: result.filter(r => r >= x)
}


## Tiny Lisp, 107 bytes

(This language was only published after this question, so this answer runs out of competition. Not that it had any chance to win. The language later evolved further to have more buildins than the ones I used here, but I'm staying with the version I originally implemented in 2015. This answer still works with the newer official interpreter, though it gives some warnings because I define a parameter a which shadows the new buildin a (for adding).Thanks to DLosc for the TIO link.)

(d r(q((m a)(i a(i(l(h a)m)(r m(t a))(c(h a)(r(h a)(t a))))()))))(d ds(q((b)(i b(c(h b)(r(h b)(t b)))()))))

This defines a function ds (and its recursive helper function r) which sorts its argument, which must be a list of integers.

r is not a tail-recursive function, so for very long lists this might run into a stack overflow.

Ungolfed:

(d r
(q((m a)
(i a
(i (l (h a) m)
(r m (t a))
(c (h a)
(r (h a) (t a))
)
)
()
)
) )
)
(d ds
(q(
(b)
(i b
(c (h b)
(r (h b) (t b))
)
()
)
) )
)


Here are some examples how to use this (with the test cases from the question):

(d list (q (args args)))
(d -
(q( (n)
(s 0 n)
) )
)

(ds (list 1 2 5 4 3 7))
(ds (list 10 (- 1) 12))
(ds (list (- 7) (- 8) (- 5) 0 (- 1) 1))
(ds (list 9 8 7 6 5))
(ds (list 10 13 17 21))
(ds (list 10 10 10 9 10))


(Yeah, -7 is not an integer literal, so we have to define a function to represent them.) Output:

list
-
(1 2 5 7)
(10 12)
(-7 -5 0 1)
(9)
(10 13 17 21)
(10 10 10 10)

• "-7 is not an integer literal" I'm still laughing, +1
– cat
Mar 21 '16 at 19:58
• Did you really use up every single character for builtins? (Except r, I guess..) Mar 22 '16 at 14:35
• @CatsAreFluffy sorry, I have problems understanding your comment. Tiny Lisp has 7 build-in functions and three build-in macros, all of them having single character-names (I guess to make the language easier to use for golfing), with parentheses and space being special syntax. Note that Tiny Lisp is not my invention. Apr 2 '16 at 15:02
• Ah, I think I get it now ... you are proposing to use a single-character name instead of ds? I guess this could be done, would save another byte. I guess I selected ds as a abbreviation for drop sort. Apr 2 '16 at 15:03
• Hey, I just noticed this. Nice job! According to meta consensus, unnamed lambda functions are a valid form of submission, so you can save 6 bytes by getting rid of (d ds and the matching ) at the end. Other golfs are possible if you want to use my current interpreter, but if you want to stick to the spec in the original question, that's fine too. :) Feb 2 '18 at 23:37

# Jelly, 5 bytes

=»\Tị


Note that the challenge predates the creation of Jelly.

Try it online!

### How it works

=»\Tị  Main link. Argument: A (list)

»\    Yield the cumulative maxima of A.
=      Perform element-by-element comparison.
Yields 1 iff A[n] = max(A[1], ..., A[n]).
T   Get all indices of truthy elements.
ị  Retrieve the items of A at those indices.


# Python 2, 41 bytes

for n in input():
if-n<=id:print n;id=-n


Try it online!

A nice to trick is to use id as the initial running maximum, since it's already initialized. Python 2 allows this weird comparison, but unfortunately functions are smaller than numbers, we instead store the running max negated.

# Python 3.8 (pre-release), 41 bytes

lambda l,m=-128:[m:=n for n in l if n>=m]


Try it online!

A nice solution using the Python 3.8+ walrus operator. We use -128 as the initial minimum since the challenge specifies the code needs to work for signed 8-bit integers.

• If we were allowed to output lists of singleton lists, I could shave this down to 38 bytes: Try it online! Dec 8 '19 at 20:54
• @isaacg The defaults on singletons mention it the output being a single value, so I think this isn't allowed by default. This is a nice idea with the walrus operator that I haven't seen before to avoid needing to initialize the mutable value
– xnor
Dec 8 '19 at 21:26
• Huh, I completely forgot that default. I've downvoted it, so I must have read it at some point. I'll go and post it as a separate answer, but I'm not going to claim the indefinite bounty because it's making use of looser I/O and therefore doesn't feel fair to me. Dec 8 '19 at 21:29

# Python 3.8 (pre-release), 38 bytes

lambda l:[l:=[n]for n in l if n>=l[0]]


Try it online!

This outputs in the format

[[-2], [0], [1], [2], [5], [5], [7]]


e.g. a list of lists containing one element each. According to this default for output, it is allowed to use a singleton list in place of a single value, so arguably this should be allowed as well.