Hands-On Data Structures and Algorithms with JavaScript

Pseudo code

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.