Page 1 of 1

Merge Sorting: A Look With Recursion Sort data using merge techniques Rate Topic: ***** 1 Votes

#1 KYA  Icon User is offline

  • g++ jameson.cpp -o beverage
  • member icon

Reputation: 3124
  • View blog
  • Posts: 19,168
  • Joined: 14-September 07

Posted 17 July 2008 - 06:51 PM

Merge Sorting

Often, computer programs need to traverse a list to find data that is relevant to the application. It makes life easier when the list, array, etc... is sorted. So far bubble, insertion, and other sort/search methods have been covered. However, there is yet another that is one of the three "foundations" (in my opinion) of search and/or sorting techniques. Merge sorting uses more memory then other sorting methods (due to the duplicate structure needed for sorting); it is not guarenteed O(n) efficiency, but more on that later.

What is it?

Merge sorting takes one array (in the below example code), copies it into a duplicate array, divides the array in half and sorts each independently, uses recursion to sort the values, and then puts the sorted array back into the original data structure. The idea is that a single call to a subset function of the initial mergeSort() function allows the program to take over without further manipulation by the user or programmer. I feel that it is a component of encapsulation; once it is written, it will hardly ever need retooling unless a more specific procedure is needed or optimization for large sets of data (then again, what doesn't need more optimization these days?) ;)

Example:

In the code we have a predefined array of integers (it is extremely easy to have user defined input, etc...)

int arrayOne[5] = {65, 72, 105, 55, 2}; //initial array that will eventually be displayed as sorted
int arrayTwo[5]; //empty array to use for sorting

mergeSort(arrayOne, arrayTwo, 5); //params, first array, duplicate, and size of array, can be dynamic



Let's go step by step through the calls:

65, 72, 105, 55, 2 is currently the original array

void mergeSort(int numbers[], int temp[], int array_size)
{
  m_sort(numbers, temp, 0, array_size - 1);
}



At this point all the "main" call does is define the limit of the array (remember an array is 0 to max - 1) and passes the information along to step one of the merge sort recursion "tree". In the next mini segment we will divide and conquer:

void m_sort(int numbers[], int temp[], int left, int right)
{
  int mid;

  if (right > left)
  {
	mid = (right + left) / 2;
	m_sort(numbers, temp, left, mid);
	m_sort(numbers, temp, (mid+1), right);

	merge(numbers, temp, left, (mid+1), right);
  }
}



We give it the original array, duplicate one, and the left and right extremes (zero and max -1). Right should always be greater then left (starting out initially). We then proceed to divide the array in "half" or as approx. to half evenly as possible. We then recursively call m_sort() to sort the array. After sorting, the two halves are then "merged" to create a "whole" array:

void merge(int numbers[], int temp[], int left, int mid, int right)
{
  int i, left_end, num_elements, tmp_pos;

  left_end = (mid - 1);
  tmp_pos = left;
  num_elements = (right - left + 1);

  while ((left <= left_end) && (mid <= right))
  {
	if (numbers[left] <= numbers[mid])
	{
	  temp[tmp_pos] = numbers[left];
	  tmp_pos += 1;
	  left += 1;
	}
	else
	{
	  temp[tmp_pos] = numbers[mid];
	  tmp_pos += 1;
	  mid += 1;
	}
  }

  while (left <= left_end)
  {
	temp[tmp_pos] = numbers[left];
	left += 1;
	tmp_pos += 1;
  }
  while (mid <= right)
  {
	temp[tmp_pos] = numbers[mid];
	mid += 1;
	tmp_pos += 1;
  }

  for (i=0; i <= num_elements; i++)
  {
	numbers[right] = temp[right];
	right -= 1;
  }
}



The combination here is basic and be taken further based on data structures or even custom classes you create! This outline illustrates the basic idea behind merge sorting. The merge is done each iteration through m_sort().

Here is a list rundown of how a merge sort works if you don't want to read all of the above:

1. If the list is of length 0 or 1, then it is already sorted. Otherwise:
2. Divide the unsorted list into two sub-lists of about half the size.
3. Sort each sub-list recursively by re-applying merge sort.
4. Merge the two sub-lists back into one sorted list.

Numerical rundown for a visual aid:

65, 72, 105, 55, 2 --original array
65, 72, 105, 55, 2 --duplicated into temp array

65, 72, 105 and 55, 2 -- array divided

65, 72 and 105 and 55, 2 -- further division for comparison

65, 72, 105 2, 55 --comparisons made, swaps executed, merged

2, 55, 65, 72, 105 -- final merged result, each step is a simple repeat of the prior ones

Efficiency:

Average case:O(n *log n), not great, but this sorting method has practical application in generally sequential data storage and the like.

Worst case:(n *log n + n O(log n)), it can get messy. ;)

Best case:Unfortunately is is often O(n* log n)

Full Code can be found HERE

Good news for programmers is that in modern systems location of data in memory contributes greatly to the speed/efficiency of this algorithm as a whole. Sequential data storage allows this sorting method to soar past quick and bubble sorting. Quicksort is regarded as the fastest of the general sorting methods, but Merge Sorting is a stable sorting method if implemented correctly. Group the data in memory together if possible and this sorting method will be well worth the time to implement/learn. Attached is a picture that does an excellent job of illustrating what exactly is taking place during merge sorting. Happy Coding!


Attached Image

This post has been edited by KYA: 18 July 2008 - 08:04 AM


Is This A Good Question/Topic? 2
  • +

Page 1 of 1