Question: Modify the code below to count the number of comparisons and the number of swaps import java.util.Random; public class MergeSort { private int[] data; private

Modify the code below to count the number of comparisons and the number of swaps

import java.util.Random;

public class MergeSort { private int[] data; private static final Random generator = new Random();

public MergeSort( int size ) { data = new int[ size ];

for ( int i = 0; i < size; i++ ) data[ i ] = 10 + generator.nextInt( 90 ); }

// call this method from main program public void sort() { sortArray( 0, data.length - 1 ); }

private void sortArray( int low, int high ) { if ( ( high - low ) >= 1 ) { int middle1 = ( low + high ) / 2; int middle2 = middle1 + 1;

sortArray( low, middle1 ); sortArray( middle2, high );

merge ( low, middle1, middle2, high ); } }

private void merge( int left, int middle1, int middle2, int right ) { int leftIndex = left; int rightIndex = middle2; int combinedIndex = left; int[] combined = new int[ data.length ]; while ( leftIndex <= middle1 && rightIndex <= right ) { if ( data[ leftIndex ] <= data[ rightIndex ] ) combined[ combinedIndex++ ] = data[ leftIndex++ ]; else combined[ combinedIndex++ ] = data[ rightIndex++ ]; } if ( leftIndex == middle2 ) while ( rightIndex <= right ) combined[ combinedIndex++ ] = data[ rightIndex++ ]; else while ( leftIndex <= middle1 ) combined[ combinedIndex++ ] = data[ leftIndex++ ];

for ( int i = left; i <= right; i++ ) data[ i ] = combined[ i ]; } }

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer
Step: 1 Unlock blur-text-image
Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock
Step: 3 Unlock

Students Have Also Explored These Related Databases Questions!