MergeSort uses divide and conquer to sort a vector (array). The same technique can be used...

 

Transcribed Image Text:

MergeSort uses divide and conquer to sort a vector (array). The same technique can be used to find the distance between the closest pair of points in a vector of points in a plane: findclosest(2DPoint[] array) { } mergesort_by_x_coord(array) return helper(array) helper(2DPoint[] array) { left, right split (array, array. length / 2) split x = (max_x_coord (left) + min_x_coord (right) ) / 2 closest left closest right findclosest (left) find closest (right) m = min(closest_left, closest_right) Points2D[] tmp = array.copy_subset (split_x-m MergeSort uses divide and conquer to sort a vector (array). The same technique can be used to find the distance between the closest pair of points in a vector of points in a plane: findclosest(2DPoint[] array) { } mergesort_by_x_coord(array) return helper(array) helper(2DPoint[] array) { left, right split (array, array. length / 2) split x = (max_x_coord (left) + min_x_coord (right) ) / 2 closest left closest right findclosest (left) find closest (right) m = min(closest_left, closest_right) Points2D[] tmp = array.copy_subset (split_x-m

Answer rating: 100% (QA)

The time complexity of this algorithm is On log2 n The mergesortbyxcoord function has a time compl... View the full answer