Based on what we have known so far about the mergesort, we can come up with the pseudo code for the implementation, as follows:

MERGE_SORT(array)
    INITIALIZE middle, left_half, right_half

    RETURN MERGE(MERGE_SORT(left_half), MERGE_SORT(right_half))

MERGE(left, right)

    INITIALIZE response

    WHILE left and right exist 

        IF left[0] < right[0]

            INSERT left[0] in result

        ELSE

            INSERT right[0] in result

    RETURN result concatenated with remainder of left and right

Note in the preceding code, we first recursively divide the input dataset, then sort and combine the dataset back. Now, let's implement this sorting algorithm.