Algorithms For Dummies

Employing better sort techniques

As sort technology improves, the sort algorithms begin taking a more intelligent 

approach to getting data into the right order. The idea is to make the problem 

smaller and easier to manage. Rather than work with an entire dataset, 

smart  sorting algorithms work with individual items, reducing the work required 

to perform the task. The following sections discuss two such smart sorting 

techniques.

---

138

 

   

  PART 2 

 Understanding the Need to Sort and Search

Rearranging data with Mergesort

A Mergesort works by applying the divide and conquer approach. The sort begins 

by breaking the dataset into individual pieces and sorting the pieces. It then 

merges the pieces in a manner that ensures that it has sorted the merged piece. 

The sorting and merging continues until the entire dataset is again a single piece. 

The worst-case sort speed of the Mergesort is O(n log n), which makes it consid-

erably faster than the techniques used in the previous section (because log n is 

always smaller than n). This sort actually requires the use of two functions. The 

first  function  works  recursively  to  split  the  pieces  apart  and  put  them  back 

together again.

data = [9, 5, 7, 4, 2, 8, 1, 10, 6, 3]

  

def mergeSort(list):

    # Determine whether the list is broken into

    # individual pieces.

    if len(list) < 2:

        return list

  

    # Find the middle of the list.

    middle = len(list)//2

    # Break the list into two pieces.

    left = mergeSort(list[:middle])

    right = mergeSort(list[middle:])

  

    # Merge the two sorted pieces into a larger piece.

    print("Left side: ", left)

    print("Right side: ", right)

    merged = merge(left, right)

    print("Merged ", merged)

    return merged

The second function performs the actual task of merging the two sides using an 

iterative process. Here’s the code used to merge the two pieces:

def merge(left, right):

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

    # it means that this is an individual item and is

    # already sorted.

    if not len(left):

        return left

    if not len(right):

        return right

  

---

CHAPTER 7