Program quicksortmain
 Integer, Parameter :: maxsize = 100
 Integer, Dimension(maxsize) :: Nums
 Character(len=20) :: filename       ! Input data file name
 Integer :: nvals = 0                ! Number of data read
 Integer :: istat                    ! Status: 0 for success
! Get the name of the file containing the input data.
Write (*,*) 'Enter the file name with the data to be read: '
Read (*,'(A20)') filename
! Open input data file.  
Open (UNIT=9, FILE=filename, STATUS='OLD', IOSTAT=istat)
! Was the OPEN successful? 
fileopen: IF ( istat == 0 ) THEN         ! Open successful
   ! The file was opened successfully, so read the data from
   ! it, and store it in the linked list.
   input: DO
      READ (9, *, IOSTAT=istat) temp      ! Get value
      IF ( istat /= 0 ) EXIT              ! Exit on end of data 
      nvals = nvals + 1                   ! Bump count
      Nums(nvals) = temp                  ! put number in array
   End DO input
  End IF fileopen
Call quicksort(Nums, nvals)
write (*,*) "Sorted array: ", (Nums(i),i=1,nvals)
! homework- do binary search on this array recursively
End Program quicksortmain

Recursive Subroutine quicksort(Arr, size)
  Integer, Intent(IN) :: size
  Integer, Dimension(size), Intent(INOUT) :: Arr
  Integer :: pos, tmp
write (*,*) "Qs called with array: ", (Arr(i),i=1,size), " size= ",size
  if (size > 1) then
    Call partition(Arr,size,Arr(1),pos) ! use A(1) to partition
write(*,*) "after partitioning: ", (Arr(i),i=1,size), " we have ", pos, &
     & " numbers less or equal to ", arr(1)
    if (pos > 1) then
       tmp = Arr(pos)  ! A(1) was the number used to partion
       Arr(pos) = Arr(1) ! put it in A(pos) now. it is biggest
       Arr(1) = tmp      ! all numbers above are less or equal.
       Call quicksort(Arr(1:pos-1), pos-1)
       if ((pos + 1) < size) then
       Call quicksort(Arr(pos+1:size), size-pos)
       end if
    else  !pos must be 1 and Arr(1) is smallest element
       Call quicksort(Arr(2:size), size-1)
    end if
 end if
end Subroutine quicksort

Subroutine partition(Marks, size, val, vpos)
  Integer, Intent(IN) :: size, val
  Integer, Intent(OUT) :: vpos  ! where partition ends when done
  Integer, Dimension(size), Intent(INOUT) :: Marks
  Integer :: i,j,k,tmp
  Logical :: move
  j = 1
  k = size
  Do
     move = .false.
     If (Marks(j) <= val) Then
        j = j + 1
        move = .true.
     End If
     If (Marks(k) > val)  Then
        k = k - 1
        move = .true.
     End If
     If (move) Cycle
     If (j >= k) EXIT
     tmp = Marks(k)
     Marks(k) = Marks(j)
     Marks(j) = tmp
     k = k - 1
     j = j + 1
  End Do
  vpos = k ! all numbers above this are <= val
End Subroutine partition


     
