Algo#24: Find min and max from given array.

Given problem of finding min and max from given array seems to be very trivial problem. But what if you are asked to do it in less than 2N-3 comparisons!

Following is simple algorithm for above problem.

Step 1: Partition given array in 2 parts.
        1.1: Compare 2 element pairs for all elements.
        1.2: Put min out of this 2 elements in list-1 and max out of this 2 elements in list-2.
Step 2: Find min & max from partial lists.
        2.1: Find running min from list-1.
        2.2: Find running max from list-2.

Though at first look, given algorithm seems to have other 2N space for storing partial list with 3N/2 -1 comparisons to find min & max. But making twist during implementation can make above algorithm to run in O(1) space complexity and 3N/2+3 comparisons only.
.

Following is implementation of above algorithm in c language with twist to reduce space complexity.

Please write comments if you find anything wrong or you want to add something more related to this topic.