Database-like join this DataFrame with the other DataFrame.

        Currently assumes the on-column(s) values are unique!

        Note there's no automatic cast if the type of the on columns differs.

        Algorithms and limitations:

        - Merge algorithms: merge-join or hash-join. Typical pros and cons apply when choosing between the two.
          Merge-join shall be used on fairly equally-sized DataFrames while a hash-join would be better when
          one of the DataFrames is (much) smaller.
        - Limitations:

          + Hash-join requires the (smaller) hashed DataFrame
            (more precisely, the on columns) to contain no duplicates!
          + Merge-join requires the on-columns to be sorted!
          + For unsorted data can only sort a single column! (current Weld limitation)

        - Sortedness. If the on-columns are sorted, merge-join does not require to sort the data so it can be
          significantly faster. Do add is_on_sorted=True if this is known to be true!
        - Uniqueness. If the on-columns data contains duplicates, the algorithm is more complicated, i.e. slow.
          Also hash-join cannot be used on a hashed (smaller) DataFrame with duplicates. Do add is_on_unique=True
          if this is known to be true!
        - Setting the above 2 flags incorrectly, e.g. is_on_sorted to True when data is in fact not sorted,
          will produce undefined results.

        Parameters
        ----------
        other : DataFrame
            With which to merge.
        how : {'inner', 'left', 'right', 'outer'}, optional
            Which kind of join to do.
        on : str or list or None, optional
            The columns from both DataFrames on which to join.
            If None, will join on the index if it has the same name.
        suffixes : tuple of str, optional
            To append on columns not in `on` that have the same name in the DataFrames.
        algorithm : {'merge', 'hash'}, optional
            Which algorithm to use. Note that for 'hash', the `other` DataFrame is the one hashed.
        is_on_sorted : bool, optional
            If we know that the on columns are already sorted, can employ faster algorithm. If False,
            the DataFrame will first be sorted by the on columns.
        is_on_unique : bool, optional
            If we know that the values are unique, can employ faster algorithm.

        Returns
        -------
        DataFrame
            DataFrame containing the merge result, with the `on` columns as index.

def merge(self, other, how='inner', on=None, suffixes=('_x', '_y'),
              algorithm='merge', is_on_sorted=False, is_on_unique=True):
        """Database-like join this DataFrame with the other DataFrame.

        Currently assumes the on-column(s) values are unique!

        Note there's no automatic cast if the type of the on columns differs.

        Algorithms and limitations:

        - Merge algorithms: merge-join or hash-join. Typical pros and cons apply when choosing between the two.
          Merge-join shall be used on fairly equally-sized DataFrames while a hash-join would be better when
          one of the DataFrames is (much) smaller.
        - Limitations:

          + Hash-join requires the (smaller) hashed DataFrame
            (more precisely, the on columns) to contain no duplicates!
          + Merge-join requires the on-columns to be sorted!
          + For unsorted data can only sort a single column! (current Weld limitation)

        - Sortedness. If the on-columns are sorted, merge-join does not require to sort the data so it can be
          significantly faster. Do add is_on_sorted=True if this is known to be true!
        - Uniqueness. If the on-columns data contains duplicates, the algorithm is more complicated, i.e. slow.
          Also hash-join cannot be used on a hashed (smaller) DataFrame with duplicates. Do add is_on_unique=True
          if this is known to be true!
        - Setting the above 2 flags incorrectly, e.g. is_on_sorted to True when data is in fact not sorted,
          will produce undefined results.

        Parameters
        ----------
        other : DataFrame
            With which to merge.
        how : {'inner', 'left', 'right', 'outer'}, optional
            Which kind of join to do.
        on : str or list or None, optional
            The columns from both DataFrames on which to join.
            If None, will join on the index if it has the same name.
        suffixes : tuple of str, optional
            To append on columns not in `on` that have the same name in the DataFrames.
        algorithm : {'merge', 'hash'}, optional
            Which algorithm to use. Note that for 'hash', the `other` DataFrame is the one hashed.
        is_on_sorted : bool, optional
            If we know that the on columns are already sorted, can employ faster algorithm. If False,
            the DataFrame will first be sorted by the on columns.
        is_on_unique : bool, optional
            If we know that the values are unique, can employ faster algorithm.

        Returns
        -------
        DataFrame
            DataFrame containing the merge result, with the `on` columns as index.

        """
        check_type(other, DataFrame)
        check_type(how, str)
        check_type(algorithm, str)
        check_str_or_list_str(on)
        check_inner_types(check_type(suffixes, tuple), str)
        check_type(is_on_sorted, bool)
        check_type(is_on_unique, bool)

        # TODO: change defaults on flag & remove after implementation
        assert is_on_unique

        # TODO: this materialization/cache step could be skipped by encoding the whole sort + merge;
        # TODO this would use the sorted on columns from weld_sort ($.1) in the join to obtain join-output-indices
        # TODO which would then be passed through a 'translation table' (of $.0) to obtain the original indices to keep
        if not is_on_sorted:
            self_df = self.sort_values(on)
            other_df = other.sort_values(on)
        else:
            self_df = self
            other_df = other

        self_reset = self_df.reset_index()
        other_reset = other_df.reset_index()
        on = _compute_on(self_df, other_df, on,
                         self_reset._gather_column_names(),
                         other_reset._gather_column_names())
        self_on_cols = self_reset[on]
        other_on_cols = other_reset[on]

        if algorithm == 'merge':
            # for left and right joins, the on columns can just be copied; no need for filter
            def fake_filter_func(x, y, z):
                return x

            if how == 'inner':
                index_filter_func = weld_iloc_indices
                data_filter_func = _series_iloc
                weld_merge_func = weld_merge_join
            elif how in {'left', 'right'}:
                index_filter_func = fake_filter_func
                data_filter_func = _series_iloc_with_missing
                weld_merge_func = weld_merge_join
            else:
                index_filter_func = fake_filter_func
                data_filter_func = _series_iloc_with_missing
                weld_merge_func = weld_merge_outer_join

            weld_objects_indexes = weld_merge_func(self_on_cols._gather_data_for_weld(),
                                                   self_on_cols._gather_weld_types(),
                                                   other_on_cols._gather_data_for_weld(),
                                                   other_on_cols._gather_weld_types(),
                                                   how, is_on_sorted, is_on_unique, 'merge-join')

            new_index = _compute_new_index(weld_objects_indexes, how, on,
                                           self_on_cols, other_on_cols,
                                           index_filter_func)

            new_data = OrderedDict()
            self_no_on = self_reset.drop(on)
            other_no_on = other_reset.drop(on)
            self_new_names, other_new_names = _compute_new_names(self_no_on._gather_column_names(),
                                                                 other_no_on._gather_column_names(),
                                                                 suffixes)

            for column_name, new_name in zip(self_no_on, self_new_names):
                new_data[new_name] = data_filter_func(self_no_on[column_name], weld_objects_indexes[0], new_index)

            for column_name, new_name in zip(other_no_on, other_new_names):
                new_data[new_name] = data_filter_func(other_no_on[column_name], weld_objects_indexes[1], new_index)

            return DataFrame(new_data, new_index)
        elif algorithm == 'hash':
            raise NotImplementedError('Not yet supported')
        else:
            raise NotImplementedError('Only merge- and hash-join algorithms are supported')