Split ‘N’ Merge

It can come in handy if there are any country restrictions or any restrictions from the side of your device on the Google App Store.A merge sort is a sorting algorithm that starts by splitting an unordered list of items into two halves called sublists. Then the algorithm repeatedly splits the sublists into smaller sublists until it reaches sublists of single elements. These single element sublists are then merged in pairs to form sublists of two items. In the process of merging the items are ordered. This process is repeated until, in the final step, the two ordered halves are merged together to form a single ordered list. As a result, the whole list is sorted.

The merge sort algorithm is an example of a divide and conquer approach to problem solving.

The group of cards is repeatedly split into half. The process is repeated until you have $7$ separate groups with a single card each.

Step 1

First, you split the cards in half. To do that, you find the card that is in the middle of the group. Here, there are seven cards so the middle card is in the fourth position. You then ‘split’ the list at the middle card, and create two new groups: one group with every item up to and including the middle card, and the other group with everything after the middle card. With an odd number of cards one group will be larger, in this case there is one group with four cards and another one with three.

There are two parts to a merge sort; splitting and merging.

Merging two lists

First consider an algorithm that combines two ordered lists (or single item lists) by merging the items into a single ordered list. The algorithm is shown in pseudocode below. Note that this version merges the items in ascending order.

The subroutine takes three arguments:

• merged – the list that will hold the ordered items after merging the two lists
• list_1 – the first list to be merged
• list_2 – the second list to be merged

• Explanation

  The subroutine is merging two ordered lists (list_1 and list_2), into a single list (merged). It needs a set of variables to keep track of where it is in each list:

  • The variable index_1 keeps track of the current position in list_1
  • The variable index_2 keeps track of the current position in list_2
  • The variable index_merged keeps track of the current position in merged

  The subroutine merges the lists as follows:

  The first while loop

  • The values from list_1[index_1] and list_2[index_2] are compared
  • The lower of the two values is written to the merged list merged at the next empty position indicated by index_merged
  • The pointer for the list that the item came from is incremented by 1;
    • if the item came from list1, index_1 is incremented by 1;
    • if the item came from list_2, index_2 is incremented by 1
  • The comparison and merging continues until one list is completely empty

  The second while loop:

  Any remaining items from list_1 are added to merged; remember that they are already in the right order. This prevents unnecessary computational steps, as the subroutine doesn’t need to compare items that are already sorted.

  The third while loop:

  Any remaining items from list_2 are added to merged; remember that they are already in the right order.

  Splitting and merging using recursion

  To implement the full merge sort algorithm, you need the subroutine. The algorithm for the merge_sort subroutine is recursive. It uses the merge subroutine that is described above to merge the sublists that are created as the algorithm progresses.

  The subroutine takes one argument:

  • items – the list of items that you want to sort