applied merge sort logic

I'm trying to solve a problem where I am to use merge sort to get the following case: in an array of n elements

get the lowest number on an array and then get the biggest number SO their subtraction (or difference between those numbers is biggest)

for example: n = 8 arr {7,8,10,20,4,19,50,70} I want to get 4 and 70, because their difference is 66 It really doesn't matter if I get the lowest and the biggest numbers, I only care for the biggest difference in their subtraction. ALSO, THE FIRST NUMBER MUST BE LOWEST THAN THE SECOND ONE, 70 and 4 is not allowed.

because this problem requires me to modify merge sort code, I was thinking: 1) get all the numbers divided into开发者_StackOverflow中文版 arrays of 1, 2) compare the i number in the array to the i+1 number, and if i number is lowest then get their difference and keep moving through all the positions in the array.

what do you think? also I'm having problem with setting the base case :S please help!

Merge-sort's philosophy is to merge results from smaller segments into bigger ones.

In merge-sort, first you merge 2 elements (2 arrays of 1 element) into a sorted array of 2 elements, and then merge 2 sorted arrays of 2 elements into a sorted array of 4 elements (because the 2 arrays are sorted, you only need to traverse and compare, smaller elements always come first in both arrays in an ascending sort), and then merge 2 sorted arrays of 4 elements into a sorted array of 8 elements.

|   |   |   |   |   |   |   |   |
|sorted |       |       |       |
|sorted         |               |
|sorted                         |

Now, you only need to find the largest and the smallest, thus, you only need to find the largest and smallest in 2 elements. Compare the 2 largest elements from 2 arrays of 2 elements and find the larger, and then compare the 2 largest elements from 2 arrays of 4 elements and find the larger, and so forth. (Same for the small side.)

|   |   |   |   |   |   |   |   |
|S     L|       |       |       |
|Smllst    Lrgst|               |
|only need to care about S & L  |

In other words, you no longer sort the whole array, but find the largest and smallest and merge results to get the final answer.

_{I think it is a little bit like quick-select to quick-sort, by the way.}

A basic merge sort sorts your array, so you easily get the biggest and smallest numbers. But you're just trying to modify the array so that you only get the biggest and smallest numbers -- you don't care about the ones in the middle. They're effectively garbage, once you identify them.

How can you identify if a number you're looking at is useless? Well, if it's the case that it's both not the smallest and not the biggest number in your current scope.

Start by looking at the psuedo-code for merge sort. What are the smallest changes you can make to more closely solve this problem?