Is there any functions for sorted list?

[mola-T]

Like inserting an element in a sorted list and returns the new sorted list

or

combining two sorted list and returns a new sorted list?

[Fuco1]

I don't think so. We can add -insert-sorted and -union-sorted which would use < for comparing and a -by versions which would also take a comparator.

Do you want to try to write a patch? (or anyone else? Otherwise I'll put it on my queue later this week)

[mola-T]

Something like this?

(defun -insert-sorted (list item pred)
  (cond
   ((funcall pred item (car list))
    (-concat (cons item nil) list))
   ((funcall pred (car (last list)) item)
    (-concat list (cons item nil)))
   (t
    (let ((min 0)
          (max (- (length list) 1)))
      (while (> (- max min) 1)
        (if (funcall pred (nth (+ (/ (- max min) 2) min) list) item)
            (setq min (+ (/ (- max min) 2) min))
          (setq max (+ (/ (- max min) 2) min))))
      (-insert-at max item list)))))

[Fuco1]

Thanks! A couple notes though:

1. Binary search is a nice idea, but with linked lists it's no better than just a linear scan (nth is O(n)), and much more complicated).
2. Instead of (-concat (cons item nil) list) you can do (cons item list). Also (cons item nil) is the same as (list item)

I think something like using -split-with and then concating with the new item in the middle should work fine.

In general, dash guidelines are "clarity over speed" until someone complains it's too slow.

[mola-T]

I am not sure whether a binary search is beneficial.

Binary search through link list : iteration is O(n) with comparison O(log n).

Linear scan: iteration is O(n) with comparison O(n).

I think there may be benefit when list is long or comparison is not a simple comparison, say comparing a string entry in a structure with case ignored or even string-lessp is not simple.

[Fuco1]

Right, but isn't your code binary search? Or we're misunderstanding each other.

[mola-T]

Yeah binary search is still good when list is long or comparison is not a simple comparison.

When list is short, it doesn't matter what method we use.

Anyway, I leave the job for you. :stuck_out_tongue_closed_eyes:

Finally, thanks for this awesome library, many other awesome packages can happen. Thank you.