Why we divide arrays till one element in merge sort

Question

I am reading merge sort algorithm. I have a question

Suppose we have a following list

list = 5 4 1 3 6 8 9 7

First divide list into 4 -4 elements. We call left and right side list

5 4 1 3 and 6 8 9 7

Then divide 5 4 1 3 into following

5 4 and 1 3

Then divide 5 and 4 into

5 4

When sorting we will start sorting from the last step and go till step 1 (where we have 4-4 elements)

Question: Anyways when we divide list till 1-1 elements and we sort and merge list at everymoment then why not divide the list till 4-4 elements only. Because in this case too we will do the merge of the list. Why to iterate till 1-1 element

Answer 1

In theory, it's because the merge procedure needs to take two sorted lists. A 4-elements list isn't sorted, while a one-element list is.

In practice, we don't split lists to one-element. Because merge sort isn't the most efficient sorting algorithm for small lists, insertion sort is. So the common optimization is to use insertion sort to sort small lists, and merge them with merge sort.

Answer 2

Because if you do it the merge-sort way, there exists an invariant that says that a merged list (after splitting) is sorted, meaning that at every level after merging the splitted lists, the merged lists are ordered.

If you merge right after splitting into 4-4 for instance, will compare the first items of both lists, while both of those values are probably not the smallest values of those splitted lists, meaning you'll end up with a result list that has an ordering that is most likely not sorted.

Answer 3

1-element list is sorted naturally. We merge two 1-element sorted lists to get 2-elements sorted list, then merge 2-elements sorted lists to get 4-elements sorted list and so on.

Merge procedure is intended for sorted lists, so we can not apply merge to unsorted 5 4 1 3 and 6 8 9 7 lists