-module(recursive).

-export([partition/4, quick_sort/1]).

quick_sort([]) -> [];
quick_sort([Pivot | Rest]) ->
    {Smaller, Larger} = partition(Pivot, Rest, [], []),
    quick_sort(Smaller) ++ [Pivot] ++ quick_sort(Larger).

partition(_, [], Smaller, Larger) -> {Smaller, Larger};
partition(Pivot, [H | T], Smaller, Larger) ->
    if H =< Pivot ->
           partition(Pivot, T, [H | Smaller], Larger);
       H > Pivot -> partition(Pivot, T, Smaller, [H | Larger])
    end.

quick_sort([5, 2, 2, 7, 6, 3])
  Pivot = 5
  Rest = [2, 2, 7, 6, 3]
  {Smaller, Larger} = ???

  partition(5, [2, 2, 7, 6, 3], [], [])
    Pivot = 5
    H = 2
    T = [2, 7, 6, 3]
    Smaller = []
    Larger = []

    partition(5, [2, 7, 6, 3], [2, []], [])
      Pivot = 5
      H = 2
      T = [7, 6, 3]
      Smaller = [2, []]
      Larger = []

      partition(5, [7, 6, 3], [2, [2, []]], [])
        Pivot = 5
        H = 7
        T = [6, 3]
        Smaller = [2, [2, []]]
        Larger = []

        partition(5, [6, 3], [2, [2, []]], [7, []])
          Pivot = 5
          H = 6
          T = [3]
          Smaller = [2, [2, []]]
          Larger = [7, []]

          partition(5, [3], [2, [2, []]], [6, [7, []]])
            Pivot = 5
            H = 3
            T = []
            Smaller = [2, [2, []]]
            Larger = [6, [7, []]]

            partition(5, [], [3, [2, [2, []]]], [6, [7, []]])
              Smaller = [3, [2, [2, []]]]
              Larger = [6, [7, []]]

  {Smaller, Larger} = {[3, [2, [2, []]]], [6, [7, []]]}

  %% (1) quick_sort([3, [2, [2, []]]] = Smaller) ++ [5 = Pivot] ++ (2) quick_sort([6, [7, []]] = Larger)
  quick_sort([3, 2, 2]) ++ [5] ++ quick_sort([6, 7])

  %% Solving (1) until the end
  quick_sort([3, 2, 2]) = quick_sort([2, 2]) ++ [3] ++ quick_sort([])
    quick_sort([2, 2]) = quick_sort([2]) ++ [2] ++ quick_sort([])
      quick_sort([2]) = quick_sort([]) ++ [2] ++ quick_sort([])

  %% Solving (2) until the end
  quick_sort([6, 7]) = quick_sort([]) ++ [6] ++ quick_sort([7])
    quick_sort([7]) = quick_sort([]) ++ [7] ++ quick_sort([])

  %% Replacing the values from our first quick_sort run
  %% obs 1: quick_sort([]) == []
  %% obs 2: consider that some values are from the left side quick_sort and other from righ side quick_sort

  %% quick_sort([3, 2, 2]) ++ [5] ++ quick_sort([6, 7])
  [2] ++ [2] ++ [3] ++ [5] ++ [6] ++ [7]

  %% Result
  [2, 2, 3, 5, 6, 7]