Merge Sorting 3 Lists of Similar Size

• nshs
In summary, the conversation discusses implementing a new version of mergeSort() where 3 sorted lists, each of about the same size, are merged. There is also a brief mention of insertion sort, shellsort, and heapsort, with code examples provided for each. No equations were discussed during the conversation.

nshs

1. Implement a new version of mergeSort() where 3 sorted lists (instead of 2) of about the same size are merged.

2. No equations

3. here is what i have so far:
Code:
public final class Sort
{
/**
* Simple insertion sort.
* @param a an array of Comparable items.
*/
public static <AnyType extends Comparable<? super AnyType>>
void insertionSort( AnyType [ ] a )
{
int j;

for( int p = 1; p < a.length; p++ )
{
AnyType tmp = a[ p ];
for( j = p; j > 0 && tmp.compareTo( a[ j - 1 ] ) < 0; j-- )
a[ j ] = a[ j - 1 ];
a[ j ] = tmp;
}
}

/**
* Shellsort, using Shell's (poor) increments.
* @param a an array of Comparable items.
*/
public static <AnyType extends Comparable<? super AnyType>>
void shellsort( AnyType [ ] a )
{
int j;

for( int gap = a.length / 2; gap > 0; gap /= 2 )
for( int i = gap; i < a.length; i++ )
{
AnyType tmp = a[ i ];
for( j = i; j >= gap &&
tmp.compareTo( a[ j - gap ] ) < 0; j -= gap )
a[ j ] = a[ j - gap ];
a[ j ] = tmp;
}
}

/**
* Standard heapsort.
* @param a an array of Comparable items.
*/
public static <AnyType extends Comparable<? super AnyType>>
void heapsort( AnyType [ ] a )
{
for( int i = a.length / 2; i >= 0; i-- )  /* buildHeap */
percDown( a, i, a.length );
for( int i = a.length - 1; i > 0; i-- )
{
swapReferences( a, 0, i );            /* deleteMax */
percDown( a, 0, i );
}
}

/**
* Internal method for heapsort.
* @param i the index of an item in the heap.
* @return the index of the left child.
*/
private static int leftChild( int i )
{
return 2 * i + 1;
}

/**
* Internal method for heapsort that is used in
* deleteMax and buildHeap.
* @param a an array of Comparable items.
* @int i the position from which to percolate down.
* @int n the logical size of the binary heap.
*/
private static <AnyType extends Comparable<? super AnyType>>
void percDown( AnyType [ ] a, int i, int n )
{
int child;
AnyType tmp;

for( tmp = a[ i ]; leftChild( i ) < n; i = child )
{
child = leftChild( i );
if( child != n - 1 && a[ child ].compareTo( a[ child + 1 ] ) < 0 )
child++;
if( tmp.compareTo( a[ child ] ) < 0 )
a[ i ] = a[ child ];
else
break;
}
a[ i ] = tmp;
}

/**
* Mergesort algorithm.
* @param a an array of Comparable items.
*/
@SuppressWarnings("unchecked")
public static <AnyType extends Comparable<? super AnyType>>
void mergeSort( AnyType [ ] a )
{
AnyType [ ] tmpArray = (AnyType[]) new Comparable[ a.length ];

mergeSort( a, tmpArray, 0, a.length - 1 );
}

/**
* Internal method that makes recursive calls.
* @param a an array of Comparable items.
* @param tmpArray an array to place the merged result.
* @param left the left-most index of the subarray.
* @param right the right-most index of the subarray.
*/
private static <AnyType extends Comparable<? super AnyType>>
void mergeSort( AnyType [ ] a, AnyType [ ] tmpArray,
int left, int right )
{
if( left < right )
{
int center = ( left + right ) / 2;
mergeSort( a, tmpArray, left, center );
mergeSort( a, tmpArray, center + 1, right );
merge( a, tmpArray, left, center + 1, right );
}
}

/**
* Internal method that merges two sorted halves of a subarray.
* @param a an array of Comparable items.
* @param tmpArray an array to place the merged result.
* @param leftPos the left-most index of the subarray.
* @param rightPos the index of the start of the second half.
* @param rightEnd the right-most index of the subarray.
*/
private static <AnyType extends Comparable<? super AnyType>>
void merge( AnyType [ ] a, AnyType [ ] tmpArray, int leftPos, int rightPos, int rightEnd )
{
int leftEnd = rightPos - 1;
int tmpPos = leftPos;
int numElements = rightEnd - leftPos + 1;

// Main loop
while( leftPos <= leftEnd && rightPos <= rightEnd )
if( a[ leftPos ].compareTo( a[ rightPos ] ) <= 0 )
tmpArray[ tmpPos++ ] = a[ leftPos++ ];
else
tmpArray[ tmpPos++ ] = a[ rightPos++ ];

while( leftPos <= leftEnd )    // Copy rest of first half
tmpArray[ tmpPos++ ] = a[ leftPos++ ];

while( rightPos <= rightEnd )  // Copy rest of right half
tmpArray[ tmpPos++ ] = a[ rightPos++ ];

// Copy tmpArray back
for( int i = 0; i < numElements; i++, rightEnd-- )
a[ rightEnd ] = tmpArray[ rightEnd ];
}

/**
* Quicksort algorithm.
* @param a an array of Comparable items.
*/
public static <AnyType extends Comparable<? super AnyType>>
void quicksort( AnyType [ ] a )
{
quicksort( a, 0, a.length - 1 );
}

private static final int CUTOFF = 3;

/**
* Method to swap to elements in an array.
* @param a an array of objects.
* @param index1 the index of the first object.
* @param index2 the index of the second object.
*/
public static <AnyType> void swapReferences( AnyType [ ] a, int index1, int index2 )
{
AnyType tmp = a[ index1 ];
a[ index1 ] = a[ index2 ];
a[ index2 ] = tmp;
}

/**
* Return median of left, center, and right.
* Order these and hide the pivot.
*/
private static <AnyType extends Comparable<? super AnyType>>
AnyType median3( AnyType [ ] a, int left, int right )
{
int center = ( left + right ) / 2;
if( a[ center ].compareTo( a[ left ] ) < 0 )
swapReferences( a, left, center );
if( a[ right ].compareTo( a[ left ] ) < 0 )
swapReferences( a, left, right );
if( a[ right ].compareTo( a[ center ] ) < 0 )
swapReferences( a, center, right );

// Place pivot at position right - 1
swapReferences( a, center, right - 1 );
return a[ right - 1 ];
}

/**
* Internal quicksort method that makes recursive calls.
* Uses median-of-three partitioning and a cutoff of 10.
* @param a an array of Comparable items.
* @param left the left-most index of the subarray.
* @param right the right-most index of the subarray.
*/
private static <AnyType extends Comparable<? super AnyType>>
void quicksort( AnyType [ ] a, int left, int right )
{
if( left + CUTOFF <= right )
{
AnyType pivot = median3( a, left, right );

// Begin partitioning
int i = left, j = right - 1;
for( ; ; )
{
while( a[ ++i ].compareTo( pivot ) < 0 ) { }
while( a[ --j ].compareTo( pivot ) > 0 ) { }
if( i < j )
swapReferences( a, i, j );
else
break;
}

swapReferences( a, i, right - 1 );   // Restore pivot

quicksort( a, left, i - 1 );    // Sort small elements
quicksort( a, i + 1, right );   // Sort large elements
}
else  // Do an insertion sort on the subarray
insertionSort( a, left, right );
}

/**
* Internal insertion sort routine for subarrays
* that is used by quicksort.
* @param a an array of Comparable items.
* @param left the left-most index of the subarray.
* @param right the right-most index of the subarray.
*/
private static <AnyType extends Comparable<? super AnyType>>
void insertionSort( AnyType [ ] a, int left, int right )
{
for( int p = left + 1; p <= right; p++ )
{
AnyType tmp = a[ p ];
int j;

for( j = p; j > left && tmp.compareTo( a[ j - 1 ] ) < 0; j-- )
a[ j ] = a[ j - 1 ];
a[ j ] = tmp;
}
}

/**
* Quick selection algorithm.
* Places the kth smallest item in a[k-1].
* @param a an array of Comparable items.
* @param k the desired rank (1 is minimum) in the entire array.
*/
public static <AnyType extends Comparable<? super AnyType>>
void quickSelect( AnyType [ ] a, int k )
{
quickSelect( a, 0, a.length - 1, k );
}

/**
* Internal selection method that makes recursive calls.
* Uses median-of-three partitioning and a cutoff of 10.
* Places the kth smallest item in a[k-1].
* @param a an array of Comparable items.
* @param left the left-most index of the subarray.
* @param right the right-most index of the subarray.
* @param k the desired index (1 is minimum) in the entire array.
*/
private static <AnyType extends Comparable<? super AnyType>>
void quickSelect( AnyType [ ] a, int left, int right, int k )
{
if( left + CUTOFF <= right )
{
AnyType pivot = median3( a, left, right );

// Begin partitioning
int i = left, j = right - 1;
for( ; ; )
{
while( a[ ++i ].compareTo( pivot ) < 0 ) { }
while( a[ --j ].compareTo( pivot ) > 0 ) { }
if( i < j )
swapReferences( a, i, j );
else
break;
}

swapReferences( a, i, right - 1 );   // Restore pivot

if( k <= i )
quickSelect( a, left, i - 1, k );
else if( k > i + 1 )
quickSelect( a, i + 1, right, k );
}
else  // Do an insertion sort on the subarray
insertionSort( a, left, right );
}

private static final int NUM_ITEMS = 1000;
private static int theSeed = 1;

private static void checkSort( Integer [ ] a )
{
for( int i = 0; i < a.length; i++ )
if( a[ i ] != i )
System.out.println( "Error at " + i );
System.out.println( "Finished checksort" );
}

public static void main( String [ ] args )
{
Integer [ ] a = new Integer[ NUM_ITEMS ];
for( int i = 0; i < a.length; i++ )
a[ i ] = i;

for( theSeed = 0; theSeed < 20; theSeed++ )
{
Random.permute( a );
Sort.insertionSort( a );
checkSort( a );

Random.permute( a );
Sort.heapsort( a );
checkSort( a );

Random.permute( a );
Sort.shellsort( a );
checkSort( a );

Random.permute( a );
Sort.mergeSort( a );
checkSort( a );

Random.permute( a );
Sort.quicksort( a );
checkSort( a );

Random.permute( a );
Sort.quickSelect( a, NUM_ITEMS / 2 );
System.out.println( a[ NUM_ITEMS / 2 - 1 ] + " " + NUM_ITEMS / 2 );
}
}
}

Last edited by a moderator:
Welcome to the PF.

I added code tags to your post for readability. You can click QUOTE on your post to see how to use code tags.

1. What is merge sorting?

Merge sorting is a popular sorting algorithm that works by dividing a list into smaller sublists, sorting those sublists, and then merging them back together to create a sorted list.

2. How does merge sorting work?

Merge sorting works by first dividing a list into smaller sublists, then sorting those sublists using a comparison operation, and finally merging the sorted sublists back together to create a sorted list.

3. What are the advantages of using merge sorting?

One advantage of merge sorting is that it has a time complexity of O(nlogn), making it more efficient than other sorting algorithms for larger lists. It is also a stable sorting algorithm, meaning that elements with equal values will retain their original order after sorting.

4. Are there any limitations to merge sorting?

One limitation of merge sorting is that it requires additional memory space to store the sublists and the merged list, making it less efficient for sorting large datasets. Additionally, merge sorting is not suitable for sorting data that is constantly changing, as it requires the entire list to be re-sorted each time a change is made.

5. How can merge sorting be used to sort 3 lists of similar size?

To merge sort 3 lists of similar size, the lists can be divided into sublists and sorted separately using merge sorting. Then, the sorted sublists can be merged together into a final sorted list of all the elements from the original 3 lists.