!------------------------------------------------------------------------------
! EPFL/Swiss Plasma Center
!------------------------------------------------------------------------------
!
! MODULE: sort
!
!> @author
!> Guillaume Le Bars EPFL/SPC
!
! DESCRIPTION: 
!> Module containing particle sorting algorithms.
!------------------------------------------------------------------------------
MODULE sort
IMPLICIT NONE

CONTAINS
!---------------------------------------------------------------------------  
!> @author 
!> Guillaume Le Bars EPFL/SPC
!
! DESCRIPTION: 
!> 
!> @brief Sorts the particles according to their z position using quick sort algorithm
!
!> @param[in] leftlimit the particles variable needing to be allocated. 
!> @param[in] right limit the maximum number of particles that will be stored in this variable      
!---------------------------------------------------------------------------  
  RECURSIVE SUBROUTINE quicksortparts(p, leftlimit, rightlimit)
  Use beam, ONLY: particles, exchange_parts
  USE constants
  TYPE(particles), INTENT(INOUT):: p
  INTEGER,INTENT(IN):: leftlimit, rightlimit
  REAL(kind=db):: pivot
  INTEGER::i, cnt, mid
    IF(leftlimit .ge. rightlimit) RETURN ! Impossible indices, return
    
    mid=(leftlimit+rightlimit)/2 ! Compute middle index

    IF(p%Z(mid).lt.p%Z(leftlimit)) CALL exchange_parts(p,leftlimit,mid)
    IF(p%Z(rightlimit).lt.p%Z(leftlimit)) CALL exchange_parts(p,leftlimit,rightlimit)
    IF(p%Z(mid).lt.p%Z(rightlimit)) CALL exchange_parts(p,rightlimit,mid)

    ! Store the pivot point for comparison
    pivot=p%Z(rightlimit)

    cnt=leftlimit
    
    ! Move all parts with Z smaller than pivot to the left of pivot
    DO i=leftlimit, rightlimit
      IF(p%Z(i) .le. pivot) THEN
        CALL exchange_parts(p, i,cnt)
        cnt=cnt+1
      END IF
    END DO

    ! Quicksort the sub-arrays
    CALL quicksortparts(p, leftlimit,cnt-2)
    CALL quicksortparts(p, cnt,rightlimit)

  END SUBROUTINE quicksortparts

!---------------------------------------------------------------------------  
!> @author 
!> Guillaume Le Bars EPFL/SPC
!
! DESCRIPTION: 
!> 
!> @brief Sorts the particles according to their index in the poisson solver grid.
!
!> @param[in] leftlimit the particles variable needing to be allocated. 
!> @param[in] right limit the maximum number of particles that will be stored in this variable      
!---------------------------------------------------------------------------  
  SUBROUTINE gridsort(p)
  USE beam
  TYPE(particles), INTENT(INOUT):: p
  !CALL creat_parts
  IF(p%Nploc .gt. 0 ) THEN

  END IF

  END SUBROUTINE gridsort

END MODULE sort