(defun quicksort-array (data key &optional (direction 1))
  "quicksort-array performs a quicksort on the given key (0 indexed) in each row, such that the matrix is eventually sorted by the given key. Direction is either 1 or 0: 1 is greatest to smallest, 0 is smallest to greatest."
  (let ((pivotvector (make-array (array-dimension data  1) :initial-element nil))
        (lesser (make-array (list (array-dimension data 0) (array-dimension data 1)) :initial-element nil))
        (greater (make-array (list (array-dimension data 0) (array-dimension data 1)) :initial-element nil))
        (rows.lesser 0)
        (rows.greater 0)
        (x (array-dimension data 0))
        (y (array-dimension data 1)))
    (if (<= x 1)
        (return-from quicksort-array data))
    ;;set pivot
    (dotimes (j y)
      (setf (aref pivotvector j) (aref data (- x 1) j)))
    (setf data (adjust-array data (list (- x 1)  y)))
    (setf x (array-dimension data 0))
    ;;iteration!
    (dotimes (i x)
      (cond ((<= (aref data i key) (aref pivotvector key))
             (dotimes (j y)
               (setf (aref lesser rows.lesser j) (aref data i j)))
             (setf rows.lesser (+ rows.lesser 1)))

            ((> (aref data i key) (aref pivotvector key))
             (dotimes (j y)
               (setf (aref greater rows.greater j) (aref data i j)))
             (setf rows.greater (+ rows.greater 1)))))
    ;;adjust matrices
    (setf lesser (adjust-array lesser (list rows.lesser y)))
    (setf greater (adjust-array greater (list rows.greater y)))
    ;;recursion
    (cond ((= direction 1)
           (array-concat (quicksort-array greater key direction) pivotvector (quicksort-array lesser key direction)))
          ((= direction 0)
           (array-concat (quicksort-array lesser key direction) pivotvector (quicksort-array greater key direction))))))

(defun array-concat (a1 vector a3)
  "array-append: returns a new array with all elements of a1 vector a3 in it. Note: the row size must be the same for all arrays"
  (let ((arr (make-array (list (+ (array-dimension a1 0) 1 (array-dimension a3 0)) (array-dimension a1 1)) :initial-element nil))
        (currow -1))
    (dotimes (i (array-dimension a1 0))
      (setf currow (+ currow 1)) 
      (dotimes (j (array-dimension a1 1))
        (setf (aref arr currow j) (aref a1 i j))))
    
    (setf currow (+ currow 1)) 
    (dotimes (j (array-dimension vector 0))
      (setf (aref arr currow j) (aref vector j)))
    
    (dotimes (i (array-dimension a3 0))
      (setf currow (+ currow 1)) 
      (dotimes (j (array-dimension a3 1))
        (setf (aref arr currow j) (aref a3 i j))))
    arr))

(deftest test-quicksort()
  (check
    (let ((x (quicksort-array
              (make-array '(5 2) :initial-contents '((1 5)
                                                     (2 4)
                                                     (3 3)
                                                     (4 2)
                                                     (5 1)))
              1))
          (veracity t))
      (dotimes (i (- (array-dimension x 0) 1) veracity)
        (cond ((< (aref x i (- (array-dimension x 1) 1))
                  (aref x (+ i 1) (- (array-dimension x 1) 1)))
               (setf veracity nil)))))))