# Better function for collections

What you need is to have `insert-x`

working on regular list (ie. `'()`

or nil) and rewriting `bubble-sort`

to create the same type as input using `empty`

function.

`empty`

returns empty collection of the same type:

```
(class (empty [1 2]))
;; => clojure.lang.PersistentVector
(class (empty #{1 2}))
;; => clojure.lang.PersistentHashSet
(class (empty '(1 2)))
;; => clojure.lang.PersistentList$EmptyList
```

Your `bubble-sort`

can look this way:

```
(defn bubble-sort [coll]
"Insert x into a sorted collection"
(into (empty coll) (reduce insert-x nil coll)))
```

This way you can get rid of all type checks inside `insert-x`

i guess you're overthinking it.

you have two tasks:

- insert item at the proper position inside a sorted collection
- return vector for input vector and list for input list

first of all, i would rewrite the `insert-x`

like this for example:

```
(defn insert-x [sorted-coll x]
(let [[l r] (split-with #(<= % x) sorted-coll)]
`(~@l ~x ~@r)))
```

notice, it does more or less the same that your variant does: taking values until the desired positions, and then concatenating left and right parts with `x`

between them. notice also, it always produces properly sorted list, independent from the input type.

```
user> (insert-x [1 3 5 7 9] 10)
;;=> (1 3 5 7 9 10)
user> (insert-x [1 3 5 7 9] 0)
;;=> (0 1 3 5 7 9)
user> (insert-x [1 3 5 7 9] 4)
;;=> (1 3 4 5 7 9)
```

so, the next thing you need, is just to reduce input and return the properly typed result:

```
(defn my-sort [coll]
(let [sorted (reduce insert-x () coll)]
(if (vector? coll)
(vec sorted)
sorted)))
user> (my-sort '(0 3 1 4 2 5 10 7))
;;=> (0 1 2 3 4 5 7 10)
user> (my-sort [0 3 1 4 2 5 10 7])
;;=> [0 1 2 3 4 5 7 10]
user> (my-sort ())
;;=> ()
user> (my-sort [])
;;=> []
```

Thank you both!

I took both of your answers and generated this solution:

```
(defn insert-x [sq x]
(apply concat (interleave (split-with #(<= % x) sq) [[x] []])))
(defn bubble-sort [sq]
((if (vector? sq) vec identity)
(reduce insert-x () sq)))
```

Test:

```
user=> (bubble-sort '(0 2 8 3 9 7))
(0 2 3 7 8 9)
user=> (bubble-sort [0 2 8 3 9 7])
[0 2 3 7 8 9]
```

Or probably even better readable:

```
(defn insert [q x]
(let [[l r] (split-with #(< % x) sq)]
(concat l [x] r)))
(defn bubble-sort [sq]
((if (vector? sq) vec identity)
(reduce insert () sq)))
```

Or:

```
(defn insert [sq x]
(let [[l r] (split-with #(< % x) sq)]
`(~@l ~x ~@r)))
(defn intoo [x sq] ;; direction neutral `into`
(into x (into x sq)))
(defn bubble-sort [sq]
(intoo (empty sq) (reduce insert () sq)))
```

`intoo`

is needed because of

```
(into () '(1 2 3)) ;;=> '(3 2 1)
(into () [1 2 3]) ;;=> '(3 2 1)
(into [] '(1 2 3)) ;;=> [1 2 3]
(into [] [1 2 3]) ;;=> [1 2 3]
# `into` uses `conj` underneath!
```

Apply two times successively `into`

fixes this:

```
(into () (into () '(1 2 3))) ;; '(1 2 3)
(into () (into () [1 2 3])) ;; '(1 2 3)
(into [] (into [] '(1 2 3))) ;; [1 2 3]
(into [] (into [] [1 2 3])) ;; [1 2 3]
```

Thus `intoo`

is kind of a direction neutral version of `into`

.

Actually, the most performance efficient version of `intoo`

might be:

```
(defmacro intoo [x sq]
(if (vector? x)
`(into ~x ~sq)
`(reverse (into ~x ~sq))))
;; user=> (intoo () '(1 2 3))
;; (1 2 3)
;; user=> (intoo () [1 2 3])
;; (1 2 3)
;; user=> (intoo [] [1 2 3])
;; [1 2 3]
;; user=> (intoo [] '(1 2 3))
;; [1 2 3]
;; or as a function:
(defn intoo [x & args]
(if (vector? x)
(apply into x args)
(reverse (apply into x args))))
```