Moved straight on to the next sort. Tried to put together a merge sort. Got the merge function working well, but once again its not recursive. So given the input '4' '3' '2' '1'. It splits it in two arrays '43' and '21'. Then sorts giving '2143'. I need it to slice up the array once more and sort. So '43' goes to '4' and '3' which is sorted to '34' and the same for '21' to '12'. I don't believe there are any issues with the code only just the fact I can't work out how to make it recursive.
Code:
#include<stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
int partition( int *A, int min, int max )
{
int mid;
if ( max > min)
{
mid = ( max + min ) / 2 ;
partition( A, min, mid ) ;
partition( A, mid + 1 , max ) ;
merge( ( A + min ), ( A + min + mid ), mid, mid ) ;
}
}
int merge( int *A, int *B, int na, int nb )
{
int *C = (int *)malloc( ( na + nb ) * sizeof( int ) ) ;
int i = 0, j = 0, k = 0 ;
while (i < na && j < nb)
{
if( A[i] < B[j] )
{
C[k] = A[i] ;
i++ ;
}
else
{
C[k] = B[j] ;
j++ ;
}
k++ ;
}
`
while ( i < na )
{
C[k] = A[i] ;
k++ ;
i++ ;
}
while ( j < nb )
{
C[k] = B[j] ;
k++ ;
j++ ;
}
/* Tests that what is in the final array is correct */
printf( "%d", C[0] ) ;
printf( "%d", C[1] ) ;
printf( "%d", C[2] ) ;
printf( "%d", C[3] ) ;
//printf( "%d", C[4] ) ;
//printf( "%d", C[5] ) ;
//printf( "%d", C[6] ) ;
//printf( "%d\n", C[7] ) ;
}
int main( void )
{
int i = 0 , min = 0 ;
int A[8] ;
int B[4] = { 5, 4, 2, 7 } ;
int C[4] = { 3, 6, 1, 8 } ;
printf( "MERGE SORT ALGORITHM\n" ) ;
printf( "Worst Case: O(nlogn) Best Case: O(n)\n" ) ;
printf( "Enter numbers to be sorted:\n" ) ;
while( i < 4 )
{
scanf( "%d", &A[i] ) ;
//printf( "%d\n", A[i] ) ;
i++ ;
}
/* To test the merge function works correctly */
//merge( B, C, 4, 4 ) ;
partition( A, min, i ) ;
}