diff --git a/glib/gsequence.c b/glib/gsequence.c
index c17357a..54f2d7d 100644
--- a/glib/gsequence.c
+++ b/glib/gsequence.c
@@ -811,6 +811,17 @@ g_sequence_search (GSequence        *seq,
  * the first item comes before the second, and a positive value if
  * the second item comes before the first.
  *
+ * <note><para>
+ * This function might fail if the data contained in the sequence was
+ * inserted unsorted with g_sequence_append() or g_sequence_prepend()
+ * and the sequences was not sorted afterwards.
+ * 
+ * So use g_sequence_insert_sorted() / g_sequence_insert_sorted_iter()
+ * to add data to your sequence or, if you add a large amount of data,
+ * you should call g_sequence_sort() / g_sequence_sort_iter() after doing
+ * the insertions with g_sequence_append() or g_sequence_prepend().
+ * </para></note>
+ *
  * Return value: an #GSequenceIter pointing to the position of the
  *     first item found equal to @data according to @cmp_func and @cmp_data.
  *
@@ -1088,6 +1099,17 @@ g_sequence_search_iter (GSequence                *seq,
  * if the first iterator comes before the second, and a positive
  * value if the second iterator comes before the first.
  *
+ * <note><para>
+ * This function might fail if the data contained in the sequence was
+ * inserted unsorted with g_sequence_append() or g_sequence_prepend()
+ * and the sequences was not sorted afterwards.
+ * 
+ * So use g_sequence_insert_sorted() / g_sequence_insert_sorted_iter()
+ * to add data to your sequence or, if you add a large amount of data,
+ * you should call g_sequence_sort() / g_sequence_sort_iter() after doing
+ * the insertions with g_sequence_append() or g_sequence_prepend().
+ * </para></note>
+ *
  * Return value: an #GSequenceIter pointing to the position of
  *     the first item found equal to @data according to @cmp_func
  *     and @cmp_data.
