-
Notifications
You must be signed in to change notification settings - Fork 5
/
insertion.ex
39 lines (30 loc) · 852 Bytes
/
insertion.ex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
defmodule ExAlgo.Sort.Insertion do
@moduledoc """
Implements sorting algorithms based on insertion.
"""
@type item :: any()
@type t :: [item()]
@doc """
Perform sort by using the merge_sort algorithm.
## Example
iex> Insertion.insertion_sort([])
[]
iex> Insertion.insertion_sort([1])
[1]
iex> Insertion.insertion_sort([3, 2, 1])
[1, 2, 3]
iex> Insertion.insertion_sort([2, 7, -1, 5])
[-1, 2, 5, 7]
"""
@spec insertion_sort(t) :: t
def insertion_sort([]), do: []
def insertion_sort([head | rest]) do
rest
|> insertion_sort()
|> insert(head)
end
@spec insert(t, item) :: t
defp insert([], item), do: [item]
defp insert([head | tail], item) when head < item, do: [head | insert(tail, item)]
defp insert(sorted_list, item), do: [item | sorted_list]
end