Quick Sort implemented in Erlang Analysis

When you want to truly understand what you are studying, you must go all the way down in the rabbit hole in order to absorb the content.

This is a step by step analysis of what is happening in a quick sort algorithm implemented in the book Learn you Some Erlang for Great Good [1].

recursive.erl

-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.

Analysis

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]

References

1. Book LYSE - chapter: Recursion