Algorithms For Dummies

  Arranging and Searching Data 

     139

    # Define variables used to merge the two pieces.

    result = []

    leftIndex = 0

    rightIndex = 0

    totalLen = len(left) 

+ len(right)

  

    # Keep working until all of the items are merged.

    while (len(result) < totalLen):

  

        # Perform the required comparisons and merge

        # the pieces according to value.

        if left[leftIndex] < right[rightIndex]:

            result.append(left[leftIndex])

            leftIndex

+= 1

        else:

            result.append(right[rightIndex])

            rightIndex

+= 1

  

        # When the left side or the right side is longer,

        # add the remaining elements to the result.

        if leftIndex == len(left) or \

            rightIndex == len(right):

                result.extend(left[leftIndex:]

                              or right[rightIndex:])

                break

  

    return result

  

mergeSort(data)

The 

print

 statements in the code help you see how the merging process works. 

Even though the process seems quite complex, it really is relatively straight-

forward when you work through the merging process shown here.

Left side:  [9]

Right side:  [5]

Merged  [5, 9]

Left side:  [4]

Right side:  [2]

Merged  [2, 4]

Left side:  [7]

Right side:  [2, 4]

Merged  [2, 4, 7]

Left side:  [5, 9]

---

140

 

   

  PART 2