Breaking Data Down

Background: Making Sorting Faster

From your previous experience with sorting, you have used nested loops to sort quantities of data. And because both of these nested loops tend to iterate roughly the same number of times as the number of quantities to be sorted, we make the rough estimate that the sorting operation will execute N² times where N is the number of items being sorted. Good Computer Science requires all of us to look for better and faster ways to conduct our business and that includes our attempts to make sorting faster and/or more efficient. For example, if we could find a way to divide the sorted list by two every time we test it, we could have a sorting process that Log₂(N) operations instead of N operations. This means for 1,000 items, it would take roughly 10 operations instead of 1,000,000 operations, and for 1,000,000 items, it would take roughtly 20 operations instead of 1,000,000,000,000 operations. Certainly, there is value here. That's the good news.

The Merge Sort Strategy

The rest of the news is that it is hard to manage data in a linear (i.e., one after the other) form so Log₂(N) cannot be achieved with simple array mangement, although there are tricks you will learn later on to make this better. However, the merge sort does take advantage of the division by two process to prepare the data for sorting. This means that log₂(N) operations can be conducted for part of the process, but N operations will still have to be conducted for the actual sorting activity. Watch this video to see how it works.

How it gets done

As you can see from the video, the first part of the process is very simple. Each recursively called method breaks its own list into two halves and when their recursive breaking process completes, each method with its own list starting from the lower index and ending with the upper index (inclusive) calls the merging operation to put them back together. The pseudo code is provideded here.

public void runMergeSort( char[] array, int lowIndex, int highIndex )

   // first, make sure the lower index of the list
   // is less than the upper index of the list

       // find the mid point of the local list

       // call the merge sort process for the left side of the list
 
       // call the merge sort process for the right side of the list

       // then merge the two lists back together as sorted data

If the lower index is not less than the upper index, there is no reason to continue; this ends the recursion as you observed in the video.

Now, About That Merging Process

Clearly, the merge sort operation is not complicated. But as might be expected, there is more work to be done. The merging process itself is where the real sorting action occurs. Let's take a look at the inner workings of that method.

public void runMerge( char[] array, int lowIndex, int midIndex, int highIndex )

    // First, using the index parameters, find the capacity needed
    // for the local array and create the array
    // Only one array is created

    // Next, load the data from the source (parameter) array
    // (between the two indices, inclusive)
    // into the newly created local array

    // Next, calculate the indices necessary to start and end
    // at the left side group and to start and end
    // at the right side group

    // Loop until either the left or right side group is out of values
    // (first of three loops)

        // check if the first available value in the left group
        // is less than the first avaliable value in the right group

            // assign the first available left value
            // to the source array's first available element

            // increment the left group index

        // otherwise, assume the right group's first available value
        // is less

            // assign the first available right value
            // to the source array's first available element

            // increment the right group index

        // increment the index for the source array
 
    // end comparison loop

    // Loop until the left side group is out of values
    // (second of three loops)

        // assign the first available left value
        // to the source array's first available element

        // increment the left group index

        // increment the source array's index

    // end left side clean out loop

    // Loop until the right side group is out of values
    // (third of three loops)

        // assign the first right value to the source array's
        // first available element

            // increment the left group index

            // increment the source array's index

    // end right side clean out loop

The merging process simply starts at the left and right sides of the loop within the range of parameters, and feeds them into the original (parameter) source array as was demonstrated in the video. The most complicated thning about this is finding the left working index and limit and the right working index and limit, and that is only a matter of drawing a picture of your array, figuring out what the indices would be, and mathematically making that happen.

Complexity

As mentioned at the beginning of this topic, Computer Scientists keep seeking better and faster ways to manage data, which of course includes sorting said data. As also noted, this method uses a divide by two strategy so half of the operation qualifies as a Log₂(N) strategy. However, the merging operations requires a series of iteration operations across the data so the second half of the strategy takes roughly N operations. For that reason, the complexity of the merge sort is considered to be N Log₂(N).

Summary

As also mentioned at the beginning of this topic, merge sorts represent a fairly significant step forward in sorting compared to the linear (N²) sorts you started with. There is more in the next topic, and much more as you extend your knowledge of data structures. Enjoy.