Page 1 of 1

Reputation:

# merge sort modified

Posted 18 January 2011 - 01:59 AM

Hi everyone!
I have a question regarding sorting algorithms. Well as I know, the insertion sort is faster than the merge sort. And I have implemented this and measured their running time for different inputs and found out that it's true the insertion sort is faster than the merge sort. Now, here's my question, is there a way in which we can modify the code of the merge sort to become as fast as insertion sort? I mean what would happen if we call for example the insertion sort as a subroutine within the merge sort code? I've been asking myself this question and thought i'd try implementing it myself, but i keep getting an error.

Anyway, here's the code:

#include <ctime>
#include <iostream>
using namespace std;

void mergeSort(int numbers[], int temp[], int array_size);
void m_sort(int numbers[], int temp[], int left, int right);
void merge(int numbers[], int temp[], int left, int mid, int right);

int main()
{
clock_t start = clock();
int arrayOne[10];
int arrayTwo[10];
int A[10];

mergeSort(arrayOne, arrayTwo, 10);

for (int i = 0; i < 10; i++)
{
cout << arrayOne[i] << " ";
}

insertion_sort(A,10);
for(int x=0;x<10;x++)
{
cout << "The modified merge sort" << endl;
cout << A[x] << endl;
}

clock_t ends = clock();
cout << "Running Time : " << (double) (ends - start) / CLOCKS_PER_SEC << endl;
return 0;
}
void insertion_sort(int x[],int length)
{
int key,i;
for(int j=1;j<length;j++)
{
key=x[j];
i=j-1;
while(x[i]>key && i>=0)
{
x[i+1]=x[i];
i--;
}
x[i+1]=key;
}
}

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

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);
}
}

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 error I keep getting is: insertion_sort is not identified. how's that possible? I did identify it.
Is there something wrong with the code? or is the idea itself not do-able?

Is This A Good Question/Topic? 0

## Replies To: merge sort modified

### #2 Munawwar

• D.I.C Regular

Reputation: 161
• Posts: 457
• Joined: 20-January 10

## Re: merge sort modified

Posted 18 January 2011 - 04:05 AM

void mergeSort(int numbers[], int temp[], int array_size);
void m_sort(int numbers[], int temp[], int left, int right);
void merge(int numbers[], int temp[], int left, int mid, int right);

int main()
{
...
insertion_sort(A,10);
...
}
void insertion_sort(int x[],int length)
{
...
}

Where is the forward declaration for insertion_sort? If you don't want to do that, then declare & implement the function before main.