def merge_intervals(i_list):
    """ Merge overlapping intervals from a (un-ordered) list

    Each interval should be represented by a tuple
        (interval_beginning_val, interval_end_val )

    :param i_list: list of tuples - original intervals

    :return: list of tuples - list of merged intervals.
    These intervals do not overlap and are sorted in ascending order.
    """

    sorted_i_list = sorted(i_list, key=lambda i_tup: i_tup[0])
    merged_i_list = []

    for idx in range(len(sorted_i_list)):

        # In the very begining, just add the left-most interval
        # to merged_i_list
        if idx == 0:
            merged_i_list.append(sorted_i_list[0])

        else:
            # Pop-out the right-most element from merged_i_list
            # [pop-outing is necessary because the interval
            # will be changed (extended) if merging is performed]
            left_i_tup = merged_i_list.pop()

            # Check for overlap with the next interval to the right from
            # sorted_i_list
            right_i_tup = sorted_i_list[idx]

            if left_i_tup[1] >= right_i_tup[0]:
                # The two intervals overlap:
                #   merge them and append the extended interval to merged_i_list
                new_tup = tuple(
                    [
                        left_i_tup[0],
                        max(left_i_tup[1], right_i_tup[1])
                    ]
                )
                merged_i_list.append(new_tup)

            else:
                # The two intervals do not overlap:
                #   return left_i_tup to its' original place in the merged_i_list and
                #   append right_i_tup - the new right-most interval to be checked for
                #   overlap with subsequent intervals from sorted_i_list
                merged_i_list.append(left_i_tup)
                merged_i_list.append(right_i_tup)

    return merged_i_list