# HG changeset patch
# User Jaroslav Hajek <highegg@gmail.com>
# Date 1234362353 -3600
# Node ID e9cb742df9eb7981e96d46c4857272f2b3438702
# Parent  dda421a1f1e62e0569e10766c19b99600ff1bd8b
imported patch sort3.diff

diff --git a/liboctave/Array-C.cc b/liboctave/Array-C.cc
--- a/liboctave/Array-C.cc
+++ b/liboctave/Array-C.cc
@@ -28,41 +28,79 @@
 // Instantiate Arrays of Complex values.
 
 #include "oct-cmplx.h"
+#include "lo-mappers.h"
 
 #include "Array.h"
 #include "Array.cc"
 #include "oct-sort.cc"
 
-static double
-xabs (const Complex& x)
+template <>
+inline bool _sort_isnan (Complex x)
 {
-  return (xisinf (x.real ()) || xisinf (x.imag ())) ? octave_Inf : abs (x);
+  return xisnan (x);
 }
 
 template <>
 bool
 octave_sort<Complex>::ascending_compare (Complex a, Complex b)
 {
-  return (xisnan (b) || (xabs (a) < xabs (b))
-	  || ((xabs (a) == xabs (b)) && (arg (a) < arg (b))));
+  return ((std::abs (a) < std::abs (b))
+	  || ((std::abs (a) == std::abs (b)) && (arg (a) < arg (b))));
 }
 
 template <>
 bool
 octave_sort<Complex>::descending_compare (Complex a, Complex b)
 {
-  return (xisnan (a) || (xabs (a) > xabs (b))
-	  || ((xabs (a) == xabs (b)) && (arg (a) > arg (b))));
+  return ((std::abs (a) > std::abs (b))
+	  || ((std::abs (a) == std::abs (b)) && (arg (a) > arg (b))));
+}
+
+static bool nan_ascending_compare (Complex x, Complex y)
+{
+  return xisnan (y) ? ! xisnan (x) : ((std::abs (x) < std::abs (x))
+	  || ((std::abs (x) == std::abs (x)) && (arg (x) < arg (x))));
+}
+
+static bool nan_descending_compare (Complex x, Complex y)
+{
+  return xisnan (x) ? ! xisnan (y) : ((std::abs (x) > std::abs (x))
+	  || ((std::abs (x) == std::abs (x)) && (arg (x) > arg (x))));
+}
+
+bool (*_sortrows_comparator (sortmode mode, 
+                             const Array<Complex>& a , bool allow_chk)) 
+(Complex, Complex)
+{
+  bool (*result) (Complex, Complex) = 0;
+
+  if (allow_chk)
+    {
+      octave_idx_type k = 0;
+      for (; k < a.numel () && ! xisnan (a(k)); k++) ;
+      if (k == a.numel ())
+        {
+          if (mode == ASCENDING)
+            result = octave_sort<Complex>::ascending_compare;
+          else if (mode == DESCENDING)
+            result = octave_sort<Complex>::descending_compare;
+        }
+    }
+
+  if (! result)
+    {
+      if (mode == ASCENDING)
+        result = nan_ascending_compare;
+      else if (mode == DESCENDING)
+        result = nan_descending_compare;
+    }
+
+  return result;
 }
 
 INSTANTIATE_ARRAY_SORT (Complex);
 
-INSTANTIATE_ARRAY_AND_ASSIGN (Complex, OCTAVE_API);
-
-INSTANTIATE_ARRAY_ASSIGN (Complex, double, OCTAVE_API)
-INSTANTIATE_ARRAY_ASSIGN (Complex, int, OCTAVE_API)
-INSTANTIATE_ARRAY_ASSIGN (Complex, short, OCTAVE_API)
-INSTANTIATE_ARRAY_ASSIGN (Complex, char, OCTAVE_API)
+INSTANTIATE_ARRAY (Complex, OCTAVE_API);
 
 #include "Array2.h"
 
diff --git a/liboctave/Array-b.cc b/liboctave/Array-b.cc
--- a/liboctave/Array-b.cc
+++ b/liboctave/Array-b.cc
@@ -33,7 +33,7 @@
 
 INSTANTIATE_ARRAY_SORT (bool);
 
-INSTANTIATE_ARRAY_AND_ASSIGN (bool, OCTAVE_API);
+INSTANTIATE_ARRAY (bool, OCTAVE_API);
 
 #include "Array2.h"
 
diff --git a/liboctave/Array-ch.cc b/liboctave/Array-ch.cc
--- a/liboctave/Array-ch.cc
+++ b/liboctave/Array-ch.cc
@@ -33,7 +33,7 @@
 
 INSTANTIATE_ARRAY_SORT (char);
 
-INSTANTIATE_ARRAY_AND_ASSIGN (char, OCTAVE_API);
+INSTANTIATE_ARRAY (char, OCTAVE_API);
 
 #include "Array2.h"
 
diff --git a/liboctave/Array-d.cc b/liboctave/Array-d.cc
--- a/liboctave/Array-d.cc
+++ b/liboctave/Array-d.cc
@@ -42,13 +42,49 @@
   return lo_ieee_isnan (x);
 }
 
+static bool nan_ascending_compare (double x, double y)
+{
+  return lo_ieee_isnan (y) ? ! lo_ieee_isnan (x) : x < y;
+}
+
+static bool nan_descending_compare (double x, double y)
+{
+  return lo_ieee_isnan (x) ? ! lo_ieee_isnan (y) : x > y;
+}
+
+bool (*_sortrows_comparator (sortmode mode, 
+                             const Array<double>& a , bool allow_chk)) 
+(double, double)
+{
+  bool (*result) (double, double) = 0;
+
+  if (allow_chk)
+    {
+      octave_idx_type k = 0;
+      for (; k < a.numel () && ! xisnan (a(k)); k++) ;
+      if (k == a.numel ())
+        {
+          if (mode == ASCENDING)
+            result = octave_sort<double>::ascending_compare;
+          else if (mode == DESCENDING)
+            result = octave_sort<double>::descending_compare;
+        }
+    }
+
+  if (! result)
+    {
+      if (mode == ASCENDING)
+        result = nan_ascending_compare;
+      else if (mode == DESCENDING)
+        result = nan_descending_compare;
+    }
+
+  return result;
+}
+
 INSTANTIATE_ARRAY_SORT (double);
 
-INSTANTIATE_ARRAY_AND_ASSIGN (double, OCTAVE_API);
-
-INSTANTIATE_ARRAY_ASSIGN (double, int, OCTAVE_API)
-INSTANTIATE_ARRAY_ASSIGN (double, short, OCTAVE_API)
-INSTANTIATE_ARRAY_ASSIGN (double, char, OCTAVE_API)
+INSTANTIATE_ARRAY (double, OCTAVE_API);
 
 #include "Array2.h"
 
diff --git a/liboctave/Array-f.cc b/liboctave/Array-f.cc
--- a/liboctave/Array-f.cc
+++ b/liboctave/Array-f.cc
@@ -42,13 +42,49 @@
   return lo_ieee_isnan (x);
 }
 
+static bool nan_ascending_compare (float x, float y)
+{
+  return lo_ieee_isnan (y) ? ! lo_ieee_isnan (x) : x < y;
+}
+
+static bool nan_descending_compare (float x, float y)
+{
+  return lo_ieee_isnan (x) ? ! lo_ieee_isnan (y) : x > y;
+}
+
+bool (*_sortrows_comparator (sortmode mode, 
+                             const Array<float>& a , bool allow_chk)) 
+(float, float)
+{
+  bool (*result) (float, float) = 0;
+
+  if (allow_chk)
+    {
+      octave_idx_type k = 0;
+      for (; k < a.numel () && ! xisnan (a(k)); k++) ;
+      if (k == a.numel ())
+        {
+          if (mode == ASCENDING)
+            result = octave_sort<float>::ascending_compare;
+          else if (mode == DESCENDING)
+            result = octave_sort<float>::descending_compare;
+        }
+    }
+
+  if (! result)
+    {
+      if (mode == ASCENDING)
+        result = nan_ascending_compare;
+      else if (mode == DESCENDING)
+        result = nan_descending_compare;
+    }
+
+  return result;
+}
+
 INSTANTIATE_ARRAY_SORT (float);
 
-INSTANTIATE_ARRAY_AND_ASSIGN (float, OCTAVE_API);
-
-INSTANTIATE_ARRAY_ASSIGN (float, int, OCTAVE_API)
-INSTANTIATE_ARRAY_ASSIGN (float, short, OCTAVE_API)
-INSTANTIATE_ARRAY_ASSIGN (float, char, OCTAVE_API)
+INSTANTIATE_ARRAY (float, OCTAVE_API);
 
 #include "Array2.h"
 
diff --git a/liboctave/Array-fC.cc b/liboctave/Array-fC.cc
--- a/liboctave/Array-fC.cc
+++ b/liboctave/Array-fC.cc
@@ -28,41 +28,79 @@
 // Instantiate Arrays of FloatComplex values.
 
 #include "oct-cmplx.h"
+#include "lo-mappers.h"
 
 #include "Array.h"
 #include "Array.cc"
 #include "oct-sort.cc"
 
-static float
-xabs (const FloatComplex& x)
+template <>
+inline bool _sort_isnan (FloatComplex x)
 {
-  return (xisinf (x.real ()) || xisinf (x.imag ())) ? octave_Float_Inf : abs (x);
+  return xisnan (x);
 }
 
 template <>
 bool
 octave_sort<FloatComplex>::ascending_compare (FloatComplex a, FloatComplex b)
 {
-  return (xisnan (b) || (xabs (a) < xabs (b))
-	  || ((xabs (a) == xabs (b)) && (arg (a) < arg (b))));
+  return ((std::abs (a) < std::abs (b))
+	  || ((std::abs (a) == std::abs (b)) && (arg (a) < arg (b))));
 }
 
 template <>
 bool
 octave_sort<FloatComplex>::descending_compare (FloatComplex a, FloatComplex b)
 {
-  return (xisnan (a) || (xabs (a) > xabs (b))
-	  || ((xabs (a) == xabs (b)) && (arg (a) > arg (b))));
+  return ((std::abs (a) > std::abs (b))
+	  || ((std::abs (a) == std::abs (b)) && (arg (a) > arg (b))));
+}
+
+static bool nan_ascending_compare (FloatComplex x, FloatComplex y)
+{
+  return xisnan (y) ? ! xisnan (x) : ((std::abs (x) < std::abs (x))
+	  || ((std::abs (x) == std::abs (x)) && (arg (x) < arg (x))));
+}
+
+static bool nan_descending_compare (FloatComplex x, FloatComplex y)
+{
+  return xisnan (x) ? ! xisnan (y) : ((std::abs (x) > std::abs (x))
+	  || ((std::abs (x) == std::abs (x)) && (arg (x) > arg (x))));
+}
+
+bool (*_sortrows_comparator (sortmode mode, 
+                             const Array<FloatComplex>& a , bool allow_chk)) 
+(FloatComplex, FloatComplex)
+{
+  bool (*result) (FloatComplex, FloatComplex) = 0;
+
+  if (allow_chk)
+    {
+      octave_idx_type k = 0;
+      for (; k < a.numel () && ! xisnan (a(k)); k++) ;
+      if (k == a.numel ())
+        {
+          if (mode == ASCENDING)
+            result = octave_sort<FloatComplex>::ascending_compare;
+          else if (mode == DESCENDING)
+            result = octave_sort<FloatComplex>::descending_compare;
+        }
+    }
+
+  if (! result)
+    {
+      if (mode == ASCENDING)
+        result = nan_ascending_compare;
+      else if (mode == DESCENDING)
+        result = nan_descending_compare;
+    }
+
+  return result;
 }
 
 INSTANTIATE_ARRAY_SORT (FloatComplex);
 
-INSTANTIATE_ARRAY_AND_ASSIGN (FloatComplex, OCTAVE_API);
-
-INSTANTIATE_ARRAY_ASSIGN (FloatComplex, float, OCTAVE_API)
-INSTANTIATE_ARRAY_ASSIGN (FloatComplex, int, OCTAVE_API)
-INSTANTIATE_ARRAY_ASSIGN (FloatComplex, short, OCTAVE_API)
-INSTANTIATE_ARRAY_ASSIGN (FloatComplex, char, OCTAVE_API)
+INSTANTIATE_ARRAY (FloatComplex, OCTAVE_API);
 
 #include "Array2.h"
 
diff --git a/liboctave/Array-i.cc b/liboctave/Array-i.cc
--- a/liboctave/Array-i.cc
+++ b/liboctave/Array-i.cc
@@ -42,34 +42,31 @@
 INSTANTIATE_ARRAY_SORT (long long);
 #endif
 
-INSTANTIATE_ARRAY_AND_ASSIGN (int, OCTAVE_API);
-INSTANTIATE_ARRAY_AND_ASSIGN (long, OCTAVE_API);
+INSTANTIATE_ARRAY (int, OCTAVE_API);
+INSTANTIATE_ARRAY (long, OCTAVE_API);
 #if defined (HAVE_LONG_LONG_INT)
-INSTANTIATE_ARRAY_AND_ASSIGN (long long, OCTAVE_API);
+INSTANTIATE_ARRAY (long long, OCTAVE_API);
 #endif
 
-INSTANTIATE_ARRAY_ASSIGN (int, short, OCTAVE_API)
-INSTANTIATE_ARRAY_ASSIGN (int, char, OCTAVE_API)
-
 INSTANTIATE_ARRAY_SORT (octave_int8);
 INSTANTIATE_ARRAY_SORT (octave_int16);
 INSTANTIATE_ARRAY_SORT (octave_int32);
 INSTANTIATE_ARRAY_SORT (octave_int64);
 
-INSTANTIATE_ARRAY_AND_ASSIGN (octave_int8, OCTAVE_API);
-INSTANTIATE_ARRAY_AND_ASSIGN (octave_int16, OCTAVE_API);
-INSTANTIATE_ARRAY_AND_ASSIGN (octave_int32, OCTAVE_API);
-INSTANTIATE_ARRAY_AND_ASSIGN (octave_int64, OCTAVE_API);
+INSTANTIATE_ARRAY (octave_int8, OCTAVE_API);
+INSTANTIATE_ARRAY (octave_int16, OCTAVE_API);
+INSTANTIATE_ARRAY (octave_int32, OCTAVE_API);
+INSTANTIATE_ARRAY (octave_int64, OCTAVE_API);
 
 INSTANTIATE_ARRAY_SORT (octave_uint8);
 INSTANTIATE_ARRAY_SORT (octave_uint16);
 INSTANTIATE_ARRAY_SORT (octave_uint32);
 INSTANTIATE_ARRAY_SORT (octave_uint64);
 
-INSTANTIATE_ARRAY_AND_ASSIGN (octave_uint8, OCTAVE_API);
-INSTANTIATE_ARRAY_AND_ASSIGN (octave_uint16, OCTAVE_API);
-INSTANTIATE_ARRAY_AND_ASSIGN (octave_uint32, OCTAVE_API);
-INSTANTIATE_ARRAY_AND_ASSIGN (octave_uint64, OCTAVE_API);
+INSTANTIATE_ARRAY (octave_uint8, OCTAVE_API);
+INSTANTIATE_ARRAY (octave_uint16, OCTAVE_API);
+INSTANTIATE_ARRAY (octave_uint32, OCTAVE_API);
+INSTANTIATE_ARRAY (octave_uint64, OCTAVE_API);
 
 #include "Array2.h"
 
diff --git a/liboctave/Array-s.cc b/liboctave/Array-s.cc
--- a/liboctave/Array-s.cc
+++ b/liboctave/Array-s.cc
@@ -36,9 +36,7 @@
 
 INSTANTIATE_ARRAY_SORT (short);
 
-INSTANTIATE_ARRAY_AND_ASSIGN (short, OCTAVE_API);
-
-INSTANTIATE_ARRAY_ASSIGN (short, char, OCTAVE_API)
+INSTANTIATE_ARRAY (short, OCTAVE_API);
 
 #include "Array2.h"
 
diff --git a/liboctave/Array.cc b/liboctave/Array.cc
--- a/liboctave/Array.cc
+++ b/liboctave/Array.cc
@@ -1987,6 +1987,13 @@
 Array<T>
 Array<T>::sort (octave_idx_type dim, sortmode mode) const
 {
+  if (dim < 0 || dim >= ndims ())
+    {
+      (*current_liboctave_error_handler)
+        ("sort: invalid dimension");
+      return Array<T> ();
+    }
+
   Array<T> m (dims ());
 
   dim_vector dv = m.dims ();
@@ -2006,12 +2013,10 @@
 
   octave_sort<T> lsort;
   
-  if (mode == ASCENDING) 
-    lsort.set_compare (octave_sort<T>::ascending_compare);
-  else if (mode == DESCENDING)
-    lsort.set_compare (octave_sort<T>::descending_compare);
+  if (mode) 
+    lsort.set_compare (mode);
   else
-    abort ();
+    return m;
 
   if (stride == 1)
     {
@@ -2098,6 +2103,13 @@
 Array<T>::sort (Array<octave_idx_type> &sidx, octave_idx_type dim, 
 		sortmode mode) const
 {
+  if (dim < 0 || dim >= ndims ())
+    {
+      (*current_liboctave_error_handler)
+        ("sort: invalid dimension");
+      return Array<T> ();
+    }
+
   Array<T> m (dims ());
 
   dim_vector dv = m.dims ();
@@ -2123,12 +2135,10 @@
   sidx = Array<octave_idx_type> (dv);
   octave_idx_type *vi = sidx.fortran_vec ();
   
-  if (mode == ASCENDING) 
-    lsort.set_compare (octave_sort<T>::ascending_compare);
-  else if (mode == DESCENDING)
-    lsort.set_compare (octave_sort<T>::descending_compare);
+  if (mode) 
+    lsort.set_compare (mode);
   else
-    abort ();
+    return m;
 
   if (stride == 1)
     {
@@ -2239,6 +2249,171 @@
 }
 
 template <class T>
+sortmode
+Array<T>::is_sorted (sortmode mode) const
+{
+  if (nelem () <= 1)
+    return ASCENDING;
+
+  const T *lo = data (), *hi = data () + nelem () - 1;
+
+  // Check for NaNs at the beginning and end.
+  if (mode != ASCENDING && _sort_isnan (*lo))
+    {
+      mode = DESCENDING;
+      do
+        ++lo;
+      while (lo < hi && _sort_isnan (*lo));
+    }
+  else if (mode != DESCENDING && _sort_isnan (*hi))
+    {
+      mode = ASCENDING;
+      do
+        --hi;
+      while (lo < hi && _sort_isnan (*hi));
+    }
+  
+  octave_sort<T> lsort;
+
+  // If mode is still unknown, compare lo and hi
+  if (! mode)
+    {
+      if (lsort.descending_compare (*lo, *hi))
+        mode = DESCENDING;
+      else if (lsort.ascending_compare (*lo, *hi))
+        mode = ASCENDING;
+      else
+        mode = ASCENDING;
+    }
+
+  lsort.set_compare (mode);
+
+  if (! lsort.is_sorted (lo, hi - lo + 1))
+    mode = UNSORTED;
+
+  return mode;
+}
+
+template <class T>
+bool (*_sortrows_comparator (sortmode mode, 
+                             const Array<T>& /* a */, bool /* allow_chk */)) (T, T)
+{
+  if (mode == ASCENDING)
+    return octave_sort<T>::ascending_compare;
+  else if (mode == DESCENDING)
+    return octave_sort<T>::descending_compare;
+  else
+    return 0;
+}
+
+template <class T>
+Array<octave_idx_type>
+Array<T>::sort_rows_idx (sortmode mode) const
+{
+  Array<octave_idx_type> idx;
+
+  octave_sort<T> lsort;
+
+  lsort.set_compare (_sortrows_comparator (mode, *this, true));
+
+  octave_idx_type r = rows (), c = cols ();
+
+  idx = Array<octave_idx_type> (r);
+
+  lsort.sort_rows (data (), idx.fortran_vec (), r, c);
+
+  return idx;
+}
+
+
+template <class T>
+sortmode 
+Array<T>::is_sorted_rows (sortmode mode) const
+{
+  octave_sort<T> lsort;
+
+  octave_idx_type r = rows (), c = cols ();
+
+  if (r <= 1 || c == 0)
+    return mode ? mode : ASCENDING;
+
+  if (! mode)
+    {
+      // Auto-detect mode.
+      bool (*compare) (T, T) = _sortrows_comparator (ASCENDING, *this, false);
+
+      octave_idx_type i;
+      for (i = 0; i < cols (); i++)
+        {
+          T l = elem (0, i), u = elem (rows () - 1, i);
+          if (compare (l, u))
+            {
+              if (mode == DESCENDING)
+                {
+                  mode = UNSORTED;
+                  break;
+                }
+              else
+                mode = ASCENDING;
+            }
+          else if (compare (u, l))
+            {
+              if (mode == ASCENDING)
+                {
+                  mode = UNSORTED;
+                  break;
+                }
+              else
+                mode = DESCENDING;
+            }
+        }
+      if (! mode && i == cols ())
+        mode = ASCENDING;
+    }
+
+  if (mode)
+    {
+      lsort.set_compare (_sortrows_comparator (mode, *this, false));
+
+      if (! lsort.is_sorted_rows (data (), r, c))
+        mode = UNSORTED;
+    }
+
+  return mode;
+
+}
+
+#define INSTANTIATE_ARRAY_SORT(T) template class octave_sort<T>;
+
+#define NO_INSTANTIATE_ARRAY_SORT(T) \
+ \
+template <> Array<T>  \
+Array<T>::sort (octave_idx_type, sortmode) const { return *this; } \
+ \
+template <> Array<T>  \
+Array<T>::sort (Array<octave_idx_type> &sidx, octave_idx_type, sortmode) const \
+{ sidx = Array<octave_idx_type> (); return *this; } \
+ \
+template <> sortmode  \
+Array<T>::is_sorted (sortmode) const  \
+{ return UNSORTED; } \
+ \
+template <> \
+bool (*_sortrows_comparator (sortmode,  \
+                             const Array<T>&, bool)) (T, T) \
+{ return 0; } \
+ \
+template <> Array<octave_idx_type>  \
+Array<T>::sort_rows_idx (sortmode) const  \
+{ return Array<octave_idx_type> (); } \
+ \
+template <> sortmode  \
+Array<T>::is_sorted_rows (sortmode) const \
+{ return UNSORTED; } \
+
+
+
+template <class T>
 Array<T>
 Array<T>::diag (octave_idx_type k) const
 {
@@ -2342,6 +2517,9 @@
   //     << prefix << "cols: " << cols () << "\n";
 }
 
+#define INSTANTIATE_ARRAY(T, API) \
+  template class API Array<T>
+
 /*
 ;;; Local Variables: ***
 ;;; mode: C++ ***
diff --git a/liboctave/Array.h b/liboctave/Array.h
--- a/liboctave/Array.h
+++ b/liboctave/Array.h
@@ -554,6 +554,15 @@
   Array<T> sort (Array<octave_idx_type> &sidx, octave_idx_type dim = 0,
 		 sortmode mode = ASCENDING) const;
 
+  // Ordering is auto-detected or can be specified.
+  sortmode is_sorted (sortmode mode = UNSORTED) const;
+
+  // Sort by rows returns only indices.
+  Array<octave_idx_type> sort_rows_idx (sortmode mode = ASCENDING) const;
+
+  // Ordering is auto-detected or can be specified.
+  sortmode is_sorted_rows (sortmode mode = UNSORTED) const;
+
   Array<T> diag (octave_idx_type k = 0) const;
 
   template <class U, class F>
@@ -578,30 +587,6 @@
   }
 };
 
-#define INSTANTIATE_ARRAY(T, API) \
-  template class API Array<T>
-
-// FIXME -- these are here for compatibility.  In the current
-// implementation, only homogeneous array assignments are actually
-// instantiated.  I think heterogeneous indexed assignments are rare
-// enough to be implemented via conversion first.  This decision may
-// still be revised, that's why these macros stay here.
-#define INSTANTIATE_ARRAY_AND_ASSIGN(T, API) \
-  INSTANTIATE_ARRAY(T, API)
-
-#define INSTANTIATE_ARRAY_ASSIGN(LT, RT, API)
-  // do nothing
-
-#define INSTANTIATE_ARRAY_SORT(T) \
-  template class octave_sort<T>; \
-
-#define NO_INSTANTIATE_ARRAY_SORT(T) \
-  template <> Array<T> Array<T>::sort \
-    (octave_idx_type, sortmode) const { return *this; } \
-  template <> Array<T> Array<T>::sort (Array<octave_idx_type> &sidx, \
-    octave_idx_type, sortmode) const \
-    { sidx = Array<octave_idx_type> (); return *this; }
-
 #endif
 
 /*
diff --git a/liboctave/ChangeLog b/liboctave/ChangeLog
--- a/liboctave/ChangeLog
+++ b/liboctave/ChangeLog
@@ -1,3 +1,23 @@
+2009-02-11  Jaroslav Hajek  <highegg@gmail.com>
+
+	* oct-sort.cc (octave_sort<T>::is_sorted, octave_sort<T>::sort_rows,
+	octave_sort<T>::is_sorted_rows): New methods.
+	* oct-sort.h: Declare them.
+
+	* Array.cc (Array<T>::is_sorted): New method.
+	(INSTANTIATE_ARRAY_SORT, NO_INSTANTIATE_ARRAY_SORT,
+	INSTANTIATE_ARRAY_AND_ASSIGN, INSTANTIATE_ARRAY): Move macros here.
+	* Array.h: Reflect changes.
+
+	* dim-vector.h (dim_vector::is_vector): New method.
+	* Array-C.cc, Array-fC.cc: Override _sort_isnan, don't check for 
+	NaN in default comparators. Provide NaN-safe comparators, override
+	_sortrows_comparator.
+	* Array-d.cc, Array-f.cc: Provide NaN-safe comparators, override
+	_sortrows_comparator.	
+	* Range.cc (Range::is_sorted): New method.
+	* Range.h: Declare it.
+
 2009-02-09  Jaroslav Hajek  <highegg@gmail.com>
 
 	* oct-sort.cc (octave_sort<T>): Rewrite for optimizations. Allow
diff --git a/liboctave/CmplxQR.cc b/liboctave/CmplxQR.cc
--- a/liboctave/CmplxQR.cc
+++ b/liboctave/CmplxQR.cc
@@ -293,7 +293,7 @@
   octave_idx_type k = q.columns ();
 
   Array<octave_idx_type> jsi;
-  Array<octave_idx_type> js = j.sort (jsi, ASCENDING);
+  Array<octave_idx_type> js = j.sort (jsi, 0, ASCENDING);
   octave_idx_type nj = js.length ();
   bool dups = false;
   for (octave_idx_type i = 0; i < nj - 1; i++)
@@ -365,7 +365,7 @@
   octave_idx_type k = q.columns ();
 
   Array<octave_idx_type> jsi;
-  Array<octave_idx_type> js = j.sort (jsi, DESCENDING);
+  Array<octave_idx_type> js = j.sort (jsi, 0, DESCENDING);
   octave_idx_type nj = js.length ();
   bool dups = false;
   for (octave_idx_type i = 0; i < nj - 1; i++)
@@ -590,7 +590,7 @@
   octave_idx_type n = r.columns ();
 
   Array<octave_idx_type> jsi;
-  Array<octave_idx_type> js = j.sort (jsi, ASCENDING);
+  Array<octave_idx_type> js = j.sort (jsi, 0, ASCENDING);
   octave_idx_type nj = js.length ();
   bool dups = false;
   for (octave_idx_type i = 0; i < nj - 1; i++)
@@ -636,7 +636,7 @@
   octave_idx_type n = r.columns ();
 
   Array<octave_idx_type> jsi;
-  Array<octave_idx_type> js = j.sort (jsi, DESCENDING);
+  Array<octave_idx_type> js = j.sort (jsi, 0, DESCENDING);
   octave_idx_type nj = js.length ();
   bool dups = false;
   for (octave_idx_type i = 0; i < nj - 1; i++)
diff --git a/liboctave/Range.cc b/liboctave/Range.cc
--- a/liboctave/Range.cc
+++ b/liboctave/Range.cc
@@ -223,8 +223,6 @@
 	retval.sort_internal (true);
       else if (mode == DESCENDING)
 	retval.sort_internal (false);
-      else
-	abort ();
     }
   else if (dim != 0)
     (*current_liboctave_error_handler) ("Range::sort: invalid dimension");
@@ -244,8 +242,6 @@
 	  retval.sort_internal (sidx, true);
       else if (mode == DESCENDING)
 	retval.sort_internal (sidx, false);
-      else
-	abort ();
     }
   else if (dim != 0)
     (*current_liboctave_error_handler) ("Range::sort: invalid dimension");
@@ -253,6 +249,17 @@
   return retval;
 }
 
+sortmode
+Range::is_sorted (sortmode mode) const
+{
+  if (rng_nelem > 1 && rng_inc < 0)
+    mode = (mode == ASCENDING) ? UNSORTED : DESCENDING;
+  else if (rng_nelem > 1 && rng_inc > 0)
+    mode = (mode == DESCENDING) ? UNSORTED : ASCENDING;
+  else
+    mode = mode ? mode : ASCENDING;
+}
+
 std::ostream&
 operator << (std::ostream& os, const Range& a)
 {
diff --git a/liboctave/Range.h b/liboctave/Range.h
--- a/liboctave/Range.h
+++ b/liboctave/Range.h
@@ -77,6 +77,8 @@
   Range sort (Array<octave_idx_type>& sidx, octave_idx_type dim = 0,
 	      sortmode mode = ASCENDING) const;
 
+  sortmode is_sorted (sortmode mode = ASCENDING) const;
+
   void set_base (double b)
   {
     if (rng_base != b)
diff --git a/liboctave/dbleQR.cc b/liboctave/dbleQR.cc
--- a/liboctave/dbleQR.cc
+++ b/liboctave/dbleQR.cc
@@ -289,7 +289,7 @@
   octave_idx_type k = q.columns ();
 
   Array<octave_idx_type> jsi;
-  Array<octave_idx_type> js = j.sort (jsi, ASCENDING);
+  Array<octave_idx_type> js = j.sort (jsi, 0, ASCENDING);
   octave_idx_type nj = js.length ();
   bool dups = false;
   for (octave_idx_type i = 0; i < nj - 1; i++)
@@ -361,7 +361,7 @@
   octave_idx_type k = q.columns ();
 
   Array<octave_idx_type> jsi;
-  Array<octave_idx_type> js = j.sort (jsi, DESCENDING);
+  Array<octave_idx_type> js = j.sort (jsi, 0, DESCENDING);
   octave_idx_type nj = js.length ();
   bool dups = false;
   for (octave_idx_type i = 0; i < nj - 1; i++)
@@ -584,7 +584,7 @@
   octave_idx_type n = r.columns ();
 
   Array<octave_idx_type> jsi;
-  Array<octave_idx_type> js = j.sort (jsi, ASCENDING);
+  Array<octave_idx_type> js = j.sort (jsi, 0, ASCENDING);
   octave_idx_type nj = js.length ();
   bool dups = false;
   for (octave_idx_type i = 0; i < nj - 1; i++)
@@ -630,7 +630,7 @@
   octave_idx_type n = r.columns ();
 
   Array<octave_idx_type> jsi;
-  Array<octave_idx_type> js = j.sort (jsi, DESCENDING);
+  Array<octave_idx_type> js = j.sort (jsi, 0, DESCENDING);
   octave_idx_type nj = js.length ();
   bool dups = false;
   for (octave_idx_type i = 0; i < nj - 1; i++)
diff --git a/liboctave/dim-vector.h b/liboctave/dim-vector.h
--- a/liboctave/dim-vector.h
+++ b/liboctave/dim-vector.h
@@ -503,6 +503,12 @@
           return retval;
         }
     }
+
+  bool is_vector (void) const
+    {
+      return (length () == 2 && (elem (0) == 1 || elem (1) == 1));
+    }
+
 };
 
 static inline bool
diff --git a/liboctave/fCmplxQR.cc b/liboctave/fCmplxQR.cc
--- a/liboctave/fCmplxQR.cc
+++ b/liboctave/fCmplxQR.cc
@@ -293,7 +293,7 @@
   octave_idx_type k = q.columns ();
 
   Array<octave_idx_type> jsi;
-  Array<octave_idx_type> js = j.sort (jsi, ASCENDING);
+  Array<octave_idx_type> js = j.sort (jsi, 0, ASCENDING);
   octave_idx_type nj = js.length ();
   bool dups = false;
   for (octave_idx_type i = 0; i < nj - 1; i++)
@@ -364,7 +364,7 @@
   octave_idx_type k = q.columns ();
 
   Array<octave_idx_type> jsi;
-  Array<octave_idx_type> js = j.sort (jsi, DESCENDING);
+  Array<octave_idx_type> js = j.sort (jsi, 0, DESCENDING);
   octave_idx_type nj = js.length ();
   bool dups = false;
   for (octave_idx_type i = 0; i < nj - 1; i++)
@@ -589,7 +589,7 @@
   octave_idx_type n = r.columns ();
 
   Array<octave_idx_type> jsi;
-  Array<octave_idx_type> js = j.sort (jsi, ASCENDING);
+  Array<octave_idx_type> js = j.sort (jsi, 0, ASCENDING);
   octave_idx_type nj = js.length ();
   bool dups = false;
   for (octave_idx_type i = 0; i < nj - 1; i++)
@@ -635,7 +635,7 @@
   octave_idx_type n = r.columns ();
 
   Array<octave_idx_type> jsi;
-  Array<octave_idx_type> js = j.sort (jsi, DESCENDING);
+  Array<octave_idx_type> js = j.sort (jsi, 0, DESCENDING);
   octave_idx_type nj = js.length ();
   bool dups = false;
   for (octave_idx_type i = 0; i < nj - 1; i++)
diff --git a/liboctave/floatQR.cc b/liboctave/floatQR.cc
--- a/liboctave/floatQR.cc
+++ b/liboctave/floatQR.cc
@@ -289,7 +289,7 @@
   octave_idx_type k = q.columns ();
 
   Array<octave_idx_type> jsi;
-  Array<octave_idx_type> js = j.sort (jsi, ASCENDING);
+  Array<octave_idx_type> js = j.sort (jsi, 0, ASCENDING);
   octave_idx_type nj = js.length ();
   bool dups = false;
   for (octave_idx_type i = 0; i < nj - 1; i++)
@@ -361,7 +361,7 @@
   octave_idx_type k = q.columns ();
 
   Array<octave_idx_type> jsi;
-  Array<octave_idx_type> js = j.sort (jsi, DESCENDING);
+  Array<octave_idx_type> js = j.sort (jsi, 0, DESCENDING);
   octave_idx_type nj = js.length ();
   bool dups = false;
   for (octave_idx_type i = 0; i < nj - 1; i++)
@@ -584,7 +584,7 @@
   octave_idx_type n = r.columns ();
 
   Array<octave_idx_type> jsi;
-  Array<octave_idx_type> js = j.sort (jsi, ASCENDING);
+  Array<octave_idx_type> js = j.sort (jsi, 0, ASCENDING);
   octave_idx_type nj = js.length ();
   bool dups = false;
   for (octave_idx_type i = 0; i < nj - 1; i++)
@@ -630,7 +630,7 @@
   octave_idx_type n = r.columns ();
 
   Array<octave_idx_type> jsi;
-  Array<octave_idx_type> js = j.sort (jsi, DESCENDING);
+  Array<octave_idx_type> js = j.sort (jsi, 0, DESCENDING);
   octave_idx_type nj = js.length ();
   bool dups = false;
   for (octave_idx_type i = 0; i < nj - 1; i++)
diff --git a/liboctave/oct-sort.cc b/liboctave/oct-sort.cc
--- a/liboctave/oct-sort.cc
+++ b/liboctave/oct-sort.cc
@@ -97,25 +97,37 @@
 #include <cassert>
 #include <algorithm>
 #include <cstring>
+#include <stack>
 
 #include "lo-mappers.h"
 #include "quit.h"
 #include "oct-sort.h"
+#include "oct-locbuf.h"
 
 template <class T>
 octave_sort<T>::octave_sort (void) : compare (ascending_compare)
 { 
   merge_init ();
-  merge_getmem (1024);
 }
 
 template <class T>
 octave_sort<T>::octave_sort (bool (*comp) (T, T)) : compare (comp) 
 { 
   merge_init (); 
-  merge_getmem (1024);
 }
-  
+
+template <class T>
+void
+octave_sort<T>::set_compare (sortmode mode)
+{
+  if (mode == ASCENDING)
+    compare = ascending_compare;
+  else if (mode == DESCENDING)
+    compare = descending_compare;
+  else
+    compare = 0;
+}
+
 template <class T>
 template <class Comp>
 void
@@ -1508,6 +1520,7 @@
 void
 octave_sort<T>::sort (T *data, octave_idx_type nel)
 {
+  merge_getmem (1024);
 #ifdef INLINE_ASCENDING_SORT
   if (compare == ascending_compare)
     sort (data, nel, std::less<T> ());
@@ -1515,7 +1528,7 @@
 #endif
 #ifdef INLINE_DESCENDING_SORT    
     if (compare == descending_compare)
-    sort (data, nel, std::greater<T> ());
+      sort (data, nel, std::greater<T> ());
   else
 #endif
     if (compare)
@@ -1526,6 +1539,7 @@
 void
 octave_sort<T>::sort (T *data, octave_idx_type *idx, octave_idx_type nel)
 {
+  merge_getmemi (1024);
 #ifdef INLINE_ASCENDING_SORT
   if (compare == ascending_compare)
     sort (data, idx, nel, std::less<T> ());
@@ -1533,13 +1547,220 @@
 #endif
 #ifdef INLINE_DESCENDING_SORT    
     if (compare == descending_compare)
-    sort (data, idx, nel, std::greater<T> ());
+      sort (data, idx, nel, std::greater<T> ());
   else
 #endif
     if (compare)
       sort (data, idx, nel, compare);
 }
 
+template <class T> template <class Comp>
+bool 
+octave_sort<T>::is_sorted (const T *data, octave_idx_type nel, Comp comp)
+{
+  const T *end = data + nel;
+  if (data != end)
+    {
+      const T *next = data;
+      while (++next != end)
+        {
+          if (comp (*next, *data))
+            break;
+          data = next;
+        }
+      data = next;
+    }
+
+  return data == end;
+}
+
+template <class T> 
+bool 
+octave_sort<T>::is_sorted (const T *data, octave_idx_type nel)
+{
+  bool retval = false;
+#ifdef INLINE_ASCENDING_SORT
+  if (compare == ascending_compare)
+    retval = is_sorted (data, nel, std::less<T> ());
+  else
+#endif
+#ifdef INLINE_DESCENDING_SORT    
+    if (compare == descending_compare)
+      retval = is_sorted (data, nel, std::greater<T> ());
+  else
+#endif
+    if (compare)
+      retval = is_sorted (data, nel, compare);
+
+  return retval;
+}
+
+// FIXME: is there really no way to make this local to the following function?
+struct sortrows_run_t
+{
+  sortrows_run_t (octave_idx_type c, octave_idx_type o, octave_idx_type n)
+    : col (c), ofs (o), nel (n) { }
+  octave_idx_type col, ofs, nel;
+};
+
+
+template <class T> template <class Comp>
+void 
+octave_sort<T>::sort_rows (const T *data, octave_idx_type *idx,
+                           octave_idx_type rows, octave_idx_type cols,
+                           Comp comp)
+{
+  OCTAVE_LOCAL_BUFFER (T, buf, rows);
+  for (octave_idx_type i = 0; i < rows; i++)
+    idx[i] = i;
+
+  if (cols == 0 || rows <= 1)
+    return;
+
+
+  // This is a breadth-first traversal.
+  typedef sortrows_run_t run_t;
+  std::stack<run_t> runs;
+
+  runs.push (run_t (0, 0, rows));
+
+  while (! runs.empty ())
+    {
+      octave_idx_type col  = runs.top ().col;
+      octave_idx_type ofs  = runs.top ().ofs;
+      octave_idx_type nel  = runs.top ().nel;
+      runs.pop ();
+      assert (nel > 1);
+
+      T *lbuf = buf + ofs;
+      const T *ldata = data + rows*col;
+      octave_idx_type *lidx = idx + ofs;
+
+      // Gather.
+      for (octave_idx_type i = 0; i < nel; i++)
+        lbuf[i] = ldata[lidx[i]];
+
+      // Sort.
+      sort (lbuf, lidx, nel, comp);
+
+      // Identify constant runs and schedule subsorts.
+      if (col < cols-1)
+        {
+          octave_idx_type lst = 0;
+          for (octave_idx_type i = 0; i < nel; i++)
+            {
+              if (comp (lbuf[lst], lbuf[i]))
+                {
+                  if (i > lst + 1)
+                    runs.push (run_t (col+1, lst, i - lst));
+                  lst = i;
+                }
+            }
+          if (nel > lst + 1)
+            runs.push (run_t (col+1, lst, nel - lst));
+        }
+    }
+}
+
+template <class T>
+void 
+octave_sort<T>::sort_rows (const T *data, octave_idx_type *idx,
+                           octave_idx_type rows, octave_idx_type cols)
+{
+#ifdef INLINE_ASCENDING_SORT
+  if (compare == ascending_compare)
+    sort_rows (data, idx, rows, cols, std::less<T> ());
+  else
+#endif
+#ifdef INLINE_DESCENDING_SORT    
+    if (compare == descending_compare)
+      sort_rows (data, idx, rows, cols, std::greater<T> ());
+  else
+#endif
+    if (compare)
+      sort_rows (data, idx, rows, cols, compare);
+}
+
+template <class T> template <class Comp>
+bool 
+octave_sort<T>::is_sorted_rows (const T *data, octave_idx_type rows, 
+                                octave_idx_type cols, Comp comp)
+{
+  if (rows <= 1 || cols == 0)
+    return true;
+    
+  // This is a breadth-first traversal.
+  const T *lastrow = data + rows*(cols - 1);
+  typedef std::pair<const T *, octave_idx_type> run_t;
+  std::stack<run_t> runs;
+
+  bool sorted = true;
+  runs.push (run_t (data, rows));
+  while (sorted && ! runs.empty ())
+    {
+      const T *lo = runs.top ().first;
+      octave_idx_type n = runs.top ().second;
+      runs.pop ();
+      if (lo < lastrow)
+        {
+          // Not the final column.
+          assert (n > 1);
+          const T *hi = lo + n, *lst = lo;
+          for (lo++; lo < hi; lo++)
+            {
+              if (comp (*lst, *lo))
+                {
+                  if (lo > lst + 1)
+                      runs.push (run_t (lst + rows, lo - lst));
+                  lst = lo;
+                }
+              else if (comp (*lo, *lst))
+                break;
+
+            }
+          if (lo == hi)
+            {
+              if (lo > lst + 1)
+                runs.push (run_t (lst + rows, lo - lst));
+            }
+          else
+            {
+              sorted = false;
+              break;
+            }
+        }
+      else
+        // The final column - use fast code.
+        sorted = is_sorted (lo, n, comp);
+    }
+      
+  return sorted;
+}
+
+template <class T>
+bool 
+octave_sort<T>::is_sorted_rows (const T *data, octave_idx_type rows, 
+                                octave_idx_type cols)
+{
+  bool retval = false;
+
+#ifdef INLINE_ASCENDING_SORT
+  if (compare == ascending_compare)
+    retval = is_sorted_rows (data, rows, cols, std::less<T> ());
+  else
+#endif
+#ifdef INLINE_DESCENDING_SORT    
+    if (compare == descending_compare)
+      retval = is_sorted_rows (data, rows, cols, std::greater<T> ());
+  else
+#endif
+    if (compare)
+      retval = is_sorted_rows (data, rows, cols, compare);
+
+  return retval;
+}
+
+
 template <class T>
 bool 
 octave_sort<T>::ascending_compare (T x, T y)
diff --git a/liboctave/oct-sort.h b/liboctave/oct-sort.h
--- a/liboctave/oct-sort.h
+++ b/liboctave/oct-sort.h
@@ -97,7 +97,7 @@
 #define MERGESTATE_TEMP_SIZE 1024
 
 // Enum for type of sort function
-enum sortmode { ASCENDING, DESCENDING };
+enum sortmode { UNSORTED = 0, ASCENDING, DESCENDING };
 
 template <class T>
 class
@@ -113,10 +113,26 @@
 
   void set_compare (bool (*comp) (T, T)) { compare = comp; }
 
+  void set_compare (sortmode mode);
+
+  // Sort an array in-place.
   void sort (T *data, octave_idx_type nel);
 
+  // Ditto, but also permute the passed indices (may not be valid indices).
   void sort (T *data, octave_idx_type *idx, octave_idx_type nel);
 
+  // Check whether an array is sorted.
+  bool is_sorted (const T *data, octave_idx_type nel);
+
+  // Sort a matrix by rows, return a permutation
+  // vector.
+  void sort_rows (const T *data, octave_idx_type *idx,
+                  octave_idx_type rows, octave_idx_type cols);
+
+  // Determine whether a matrix (as a contiguous block) is sorted by rows.
+  bool is_sorted_rows (const T *data, 
+                       octave_idx_type rows, octave_idx_type cols);
+
   static bool ascending_compare (T, T);
   static bool descending_compare (T, T);
 
@@ -241,6 +257,18 @@
   template <class Comp>
   void sort (T *data, octave_idx_type *idx, octave_idx_type nel, Comp comp);
 
+  template <class Comp>
+  bool is_sorted (const T *data, octave_idx_type nel, Comp comp);
+
+  template <class Comp>
+  void sort_rows (const T *data, octave_idx_type *idx,
+                  octave_idx_type rows, octave_idx_type cols,
+                  Comp comp);
+
+  template <class Comp>
+  bool is_sorted_rows (const T *data, octave_idx_type rows, 
+                       octave_idx_type cols, Comp comp);
+
 };
 
 template <class T>
diff --git a/scripts/ChangeLog b/scripts/ChangeLog
--- a/scripts/ChangeLog
+++ b/scripts/ChangeLog
@@ -1,3 +1,8 @@
+2009-02-11  Jaroslav Hajek  <highegg@gmail.com>
+
+	* general/sortrows.m: Employ __sortrows_idx__ when applicable,
+	gripe for sparse matrices.
+
 2009-02-11  John W. Eaton  <jwe@octave.org>
 
 	* miscellaneous/news.m: Look in octetcdir for NEWS file.
diff --git a/scripts/general/sortrows.m b/scripts/general/sortrows.m
--- a/scripts/general/sortrows.m
+++ b/scripts/general/sortrows.m
@@ -1,4 +1,5 @@
 ## Copyright (C) 2000, 2005, 2007 Daniel Calvelo
+## Copyright (C) 2009 Jaroslav Hajek
 ##
 ## This file is part of Octave.
 ##
@@ -32,10 +33,20 @@
 
   default_mode = "ascend";
   other_mode = "descend";
-  if (nargin < 2)
-    indices = [1:size(m,2)]';
-    mode(1:size(m,2)) = {default_mode};
+
+  if (issparse (m))
+    error ("sortrows: sparse matrices not yet supported");
+  endif
+
+  ## If the sort is homogeneous, we use the built-in faster algorithm.
+  if (nargin == 1)
+    i = __sortrows_idx__ (m, default_mode);
+  elseif (all (c > 0))
+    i = __sortrows_idx__ (m(:,c), default_mode);
+  elseif (all (c < 0))
+    i = __sortrows_idx__ (m(:,c), other_mode);
   else
+    ## Otherwise, fall back to the old algorithm
     for ii = 1:length (c);
       if (c(ii) < 0)
         mode{ii} = other_mode;
@@ -44,30 +55,21 @@
       endif
     endfor
     indices = abs(c(:));
-  endif
 
-  if (ischar (m))
-    s = toascii (m);
-  else
-    s = m;
+    ## Since sort is 'stable' the order of identical elements will be
+    ## preserved, so by traversing the sort indices in reverse order we
+    ## will make sure that identical elements in index i are subsorted by
+    ## index j.
+    indices = flipud (indices);
+    mode = flipud (mode');
+    i = [1:size(m,1)]';
+    for ii = 1:length (indices);
+      [trash, idx] = sort (m(i, indices(ii)), mode{ii});
+      i = i(idx);
+    endfor
   endif
 
-  ## Since sort is 'stable' the order of identical elements will be
-  ## preserved, so by traversing the sort indices in reverse order we
-  ## will make sure that identical elements in index i are subsorted by
-  ## index j.
-  indices = flipud (indices);
-  mode = flipud (mode');
-  i = [1:size(m,1)]';
-  for ii = 1:length (indices);
-    [trash, idx] = sort (s(:,indices(ii)), mode{ii});
-    s = s(idx,:);
-    i = i(idx);
-  endfor
-
-  if (ischar (m))
-    s = char (s);
-  endif
+  s = m(i,:);
 
 endfunction
 
diff --git a/src/ChangeLog b/src/ChangeLog
--- a/src/ChangeLog
+++ b/src/ChangeLog
@@ -1,3 +1,25 @@
+2009-02-11  Jaroslav Hajek  <highegg@gmail.com>
+
+	* ov.h (octave_value::issorted, octave_value::sortrows_idx,
+	octave_value::issorted_rows): New methods.
+	* ov.cc (octave_base_value::issorted, octave_base_value::sortrows_idx,
+	octave_base_value::issorted_rows): New methods.
+	* ov.cc: Declare them.
+
+	* ov-base-mat.h (octave_base_matrix::issorted, octave_base_matrix::sortrows_idx,
+	octave_base_matrix::issorted_rows): New methods.
+
+	* ov-base-diag.h (octave_base_diag::issorted, octave_base_diag::sortrows_idx,
+	octave_base_diag::issorted_rows): New methods.
+
+	* ov-perm.h (octave_perm_matrix::issorted, octave_perm_matrix::sortrows_idx,
+	octave_perm_matrix::issorted_rows): New methods.
+
+	* ov-range.h (octave_range::issorted, octave_range::sortrows_idx,
+	octave_range::issorted_rows): New methods.
+
+	* data.cc (F__sortrows_idx__, Fissorted): New defuns.
+
 2009-02-11  John W. Eaton  <jwe@octave.org>
 
 	* toplev.cc (octave_config_info): Add octetcdir to the struct.
diff --git a/src/TEMPLATE-INST/Array-sym.cc b/src/TEMPLATE-INST/Array-sym.cc
--- a/src/TEMPLATE-INST/Array-sym.cc
+++ b/src/TEMPLATE-INST/Array-sym.cc
@@ -34,6 +34,8 @@
 
 typedef symbol_record* symbol_record_ptr;
 
+NO_INSTANTIATE_ARRAY_SORT (symbol_record_ptr);
+
 INSTANTIATE_ARRAY (symbol_record_ptr, OCTINTERP_API);
 
 /*
diff --git a/src/TEMPLATE-INST/Array-tc.cc b/src/TEMPLATE-INST/Array-tc.cc
--- a/src/TEMPLATE-INST/Array-tc.cc
+++ b/src/TEMPLATE-INST/Array-tc.cc
@@ -58,9 +58,7 @@
 
 INSTANTIATE_ARRAY_SORT (octave_value);
 
-template class OCTINTERP_API Array<octave_value>;
-
-INSTANTIATE_ARRAY_ASSIGN (octave_value, octave_value, OCTINTERP_API);
+INSTANTIATE_ARRAY (octave_value, OCTINTERP_API);
 
 template class OCTINTERP_API Array2<octave_value>;
 
diff --git a/src/data.cc b/src/data.cc
--- a/src/data.cc
+++ b/src/data.cc
@@ -2,6 +2,7 @@
 
 Copyright (C) 1994, 1995, 1996, 1997, 1998, 1999, 2000, 2001, 2002,
               2003, 2004, 2005, 2006, 2007 John W. Eaton
+Copyright (C) 2009 Jaroslav Hajek
 
 This file is part of Octave.
 
@@ -5573,6 +5574,106 @@
 
 */
 
+DEFUN (__sortrows_idx__, args, ,
+  "-*- texinfo -*-\n\
+@deftypefn {Function File} {} __sortrows_idx__ (@var{a}, @var{mode})\n\
+Sort the rows of the matrix @var{a} according to the order specified\n\
+by @var{mode}, which can either be `ascend' or `descend'.\n\
+Returns the index vector.\n\
+\n\
+This function does not yet support sparse matrices.\n\
+@end deftypefn\n")
+{
+  octave_value retval;
+
+  int nargin = args.length ();
+  sortmode smode = ASCENDING;
+
+  if (nargin < 1 || nargin > 2 || (nargin == 2 && ! args(1).is_string ()))
+    {
+      print_usage ();
+      return retval;
+    }
+
+  if (nargin > 1)
+    {
+      std::string mode = args(1).string_value();
+      if (mode == "ascend")
+        smode = ASCENDING;
+      else if (mode == "descend")
+        smode = DESCENDING;
+      else
+        {
+          error ("__sortrows_idx__: mode must be either \"ascend\" or \"descend\"");
+          return retval;
+        }
+    }
+
+  octave_value arg = args(0);
+
+  if (arg.is_sparse_type ())
+    error ("__sortrows_idx__: sparse matrices not yet supported");
+  if (arg.ndims () == 2)
+    {
+      Array<octave_idx_type> idx = arg.sortrows_idx (smode);
+
+      retval = NDArray (idx, true);
+    }
+  else
+    error ("__sortrows_idx__: needs a 2-dimensional object");
+
+  return retval;
+}
+
+DEFUN (issorted, args, ,
+  "-*- texinfo -*-\n\
+@deftypefn {Function File} {} issorted (@var{a}, @var{rows})\n\
+Returns true if the array is sorted, ascending or descending.\n\
+NaNs are treated is by @code{sort}. If @var{rows} is supplied and\n\
+has the value \"rows\", checks whether the array is sorted by rows\n\
+as if output by @code{sortrows} (with no options).\n\
+\n\
+This function does not yet support sparse matrices.\n\
+@seealso{sortrows, sort}\n\
+@end deftypefn\n")
+{
+  octave_value retval;
+
+  int nargin = args.length ();
+
+  if (nargin == 1)
+    {
+      octave_value arg = args(0);
+      if (arg.dims ().is_vector ())
+        retval = args(0).issorted () != UNSORTED;
+      else
+        error ("issorted: needs a vector");
+    }
+  else if (nargin == 2)
+    {
+      if (args(1).is_string () && args(1).string_value () == "rows")
+        {
+          octave_value arg = args(0);
+          sortmode smode = ASCENDING;
+
+          if (arg.is_sparse_type ())
+            error ("issorted: sparse matrices not yet supported");
+          if (arg.ndims () == 2)
+            retval = arg.issorted_rows (smode) != UNSORTED;
+          else
+            error ("issorted: needs a 2-dimensional object");
+        }
+      else
+        error ("issorted: second argument must be \"rows\"");
+    }
+  else
+    print_usage ();
+
+  return retval;
+}
+
+
+
 /*
 ;;; Local Variables: ***
 ;;; mode: C++ ***
diff --git a/src/ov-base-diag.h b/src/ov-base-diag.h
--- a/src/ov-base-diag.h
+++ b/src/ov-base-diag.h
@@ -106,6 +106,15 @@
 		     sortmode mode = ASCENDING) const
     { return to_dense ().sort (sidx, dim, mode); }
 
+  sortmode issorted (sortmode mode = UNSORTED) const
+    { return to_dense ().issorted (mode); }
+
+  Array<octave_idx_type> sortrows_idx (sortmode mode = ASCENDING) const
+    { return to_dense ().sortrows_idx (mode); }
+
+  sortmode issorted_rows (sortmode mode = UNSORTED) const
+    { return to_dense ().issorted_rows (mode); }
+
   bool is_matrix_type (void) const { return true; }
 
   bool is_numeric_type (void) const { return true; }
diff --git a/src/ov-base-mat.h b/src/ov-base-mat.h
--- a/src/ov-base-mat.h
+++ b/src/ov-base-mat.h
@@ -124,6 +124,15 @@
 		     sortmode mode = ASCENDING) const
     { return octave_value (matrix.sort (sidx, dim, mode)); }
 
+  sortmode issorted (sortmode mode = UNSORTED) const
+    { return matrix.is_sorted (mode); }
+
+  Array<octave_idx_type> sortrows_idx (sortmode mode = ASCENDING) const
+    { return matrix.sort_rows_idx (mode); }
+
+  sortmode issorted_rows (sortmode mode = UNSORTED) const
+    { return matrix.is_sorted_rows (mode); }
+
   bool is_matrix_type (void) const { return true; }
 
   bool is_numeric_type (void) const { return true; }
diff --git a/src/ov-base-scalar.h b/src/ov-base-scalar.h
--- a/src/ov-base-scalar.h
+++ b/src/ov-base-scalar.h
@@ -108,6 +108,15 @@
       return octave_value (scalar); 
     }
 
+  sortmode issorted (sortmode mode = UNSORTED) const
+    { return mode ? mode : ASCENDING; }
+
+  Array<octave_idx_type> sortrows_idx (sortmode) const
+    { return Array<octave_idx_type> (1, 0); }
+
+  sortmode issorted_rows (sortmode mode = UNSORTED) const
+    { return mode ? mode : ASCENDING; }
+
   MatrixType matrix_type (void) const { return typ; }
   MatrixType matrix_type (const MatrixType& _typ) const
     { MatrixType ret = typ; typ = _typ; return ret; }
diff --git a/src/ov-base-sparse.h b/src/ov-base-sparse.h
--- a/src/ov-base-sparse.h
+++ b/src/ov-base-sparse.h
@@ -126,6 +126,9 @@
 		     sortmode mode = ASCENDING) const
     { return octave_value (matrix.sort (sidx, dim, mode)); }
 
+  sortmode issorted (sortmode mode = UNSORTED) const
+    { return full_value ().issorted (mode); }
+
   MatrixType matrix_type (void) const { return typ; }
   MatrixType matrix_type (const MatrixType& _typ) const
     { MatrixType ret = typ; typ = _typ; return ret; }
diff --git a/src/ov-base.cc b/src/ov-base.cc
--- a/src/ov-base.cc
+++ b/src/ov-base.cc
@@ -978,6 +978,30 @@
   return octave_value();
 }
 
+sortmode
+octave_base_value::issorted (sortmode) const
+{
+  gripe_wrong_type_arg ("octave_base_value::issorted ()", type_name ());
+
+  return UNSORTED;
+}
+
+Array<octave_idx_type>
+octave_base_value::sortrows_idx (sortmode) const
+{
+  gripe_wrong_type_arg ("octave_base_value::sortrows_idx ()", type_name ());
+
+  return Array<octave_idx_type> ();
+}
+
+sortmode
+octave_base_value::issorted_rows (sortmode) const
+{
+  gripe_wrong_type_arg ("octave_base_value::issorted_rows ()", type_name ());
+
+  return UNSORTED;
+}
+
 #define UNDEFINED_MAPPER(F) \
   octave_value \
   octave_base_value::F (void) const \
diff --git a/src/ov-base.h b/src/ov-base.h
--- a/src/ov-base.h
+++ b/src/ov-base.h
@@ -515,6 +515,12 @@
 			     octave_idx_type dim = 0,
 			     sortmode mode = ASCENDING) const;
 
+  virtual sortmode issorted (sortmode mode = UNSORTED) const;
+
+  virtual Array<octave_idx_type> sortrows_idx (sortmode mode = ASCENDING) const;
+
+  virtual sortmode issorted_rows (sortmode mode = UNSORTED) const;
+
   virtual void lock (void);
 
   virtual void unlock (void);
diff --git a/src/ov-perm.h b/src/ov-perm.h
--- a/src/ov-perm.h
+++ b/src/ov-perm.h
@@ -93,6 +93,15 @@
 		     sortmode mode = ASCENDING) const
     { return to_dense ().sort (sidx, dim, mode); }
 
+  sortmode issorted (sortmode mode = UNSORTED) const
+    { return to_dense ().issorted (mode); }
+
+  Array<octave_idx_type> sortrows_idx (sortmode mode = ASCENDING) const
+    { return to_dense ().sortrows_idx (mode); }
+
+  sortmode issorted_rows (sortmode mode = UNSORTED) const
+    { return to_dense ().issorted_rows (mode); }
+
   bool is_perm_matrix (void) const { return true; }
 
   bool is_matrix_type (void) const { return true; }
diff --git a/src/ov-range.h b/src/ov-range.h
--- a/src/ov-range.h
+++ b/src/ov-range.h
@@ -140,6 +140,15 @@
 		     sortmode mode = ASCENDING) const
     { return range.sort (sidx, dim, mode); }
 
+  sortmode issorted (sortmode mode = UNSORTED) const
+    { return range.is_sorted (mode); }
+
+  Array<octave_idx_type> sortrows_idx (sortmode) const
+    { return Array<octave_idx_type> (1, 0); }
+
+  sortmode issorted_rows (sortmode mode = UNSORTED) const
+    { return mode ? mode : ASCENDING; }
+
   bool is_real_type (void) const { return true; }
 
   bool is_double_type (void) const { return true; }
diff --git a/src/ov.h b/src/ov.h
--- a/src/ov.h
+++ b/src/ov.h
@@ -996,6 +996,15 @@
 		 sortmode mode = ASCENDING) const
     { return rep->sort (sidx, dim, mode); } 
 
+  sortmode issorted (sortmode mode = UNSORTED) const
+    { return rep->issorted (mode); }
+
+  Array<octave_idx_type> sortrows_idx (sortmode mode = ASCENDING) const
+    { return rep->sortrows_idx (mode); }
+
+  sortmode issorted_rows (sortmode mode = UNSORTED) const
+    { return rep->issorted_rows (mode); }
+
   void lock (void) { rep->lock (); }
 
   void unlock (void) { rep->unlock (); }