def _merge_2(list_, i, mid, j):
    """
    Merge the two sorted halves list_[i:mid + 1] and
    list_[mid + 1:j + 1] and return them in a new list.
    Notice that list_[mid] belongs in the left half and list_[j]
    belongs in the right half -- the indices are inclusive.

    @param list list_: list to sort
    @param int i: starting index for first half of list to sort
    @param int mid: index for middle of list to sort
    @param int j: index for end of list to sort

    >>> _merge_2([1, 3, 5, 2, 4, 6], 0, 2, 5)
    [1, 2, 3, 4, 5, 6]
    """
    result = []
    left = i
    right = mid + 1
    # Done when left > mid or when right > j; i.e.,
    # when we've finished one of the halves.
    while left <= mid and right <= j:
        if list_[left] < list_[right]:
            result.append(list_[left])
            left += 1
        else:
            result.append(list_[right])
            right += 1
    # Items left: list_[left:mid + 1]
    #             list_[right:j + 1]
    return result + list_[left:mid + 1] + list_[right:j + 1]