partition Subroutine

  subroutine partition( list, marker )
    ! ---------------------------------------------------------------------------
    !> list to be partitioned
    integer( kind=long_k ), intent(inout)  :: list(:)
    !> marker where the list is partitioned
    integer, intent(out) :: marker
    ! ---------------------------------------------------------------------------
    integer :: left, right
    integer(kind=long_k) :: pivot, temp
    ! ---------------------------------------------------------------------------

    ! set the average of first and last entry as pivot element (bug for entries
    ! < 0)
!    pivot = ( list(1) + list( size( list )))/2
    ! choose the element in the middle as pivot element
    pivot = list(size(list)/2)

    ! initialize the pointers on the entries
    left = 0
    right = size( list ) + 1

    do while( left .lt. right)
      right = right - 1
      do while( list( right ) .gt. pivot)
        right = right - 1
      end do
      left = left + 1
      do while( list( left ) .lt. pivot)
        left = left + 1
      end do
      if( left .lt. right )then
        temp = list( left )
        list(left) = list(right)
        list(right) = temp
      end if
    end do

    if( left .eq. right )then
      marker = left + 1
    else
      marker = left
    end if

  end subroutine partition