{
  "id": "qsort-1743478-b74a092d522b3e27",
  "slug": "qsort",
  "title": "qsort",
  "qid": "Q15995414",
  "lead": "is a C standard library function that implements a sorting algorithm for arrays of arbitrary objects according to a user-provided comparison function. It is named after the \"quicker sort\" algorithm (a quicksort variant due to R. S. Scowen), which was originally used to implement it in the Unix C library, although the C standard does not require it to implement quicksort. It comes from (or in C++ Standard Library). The ability to operate on different kinds of data (polymorphism) is achieved by taking a function pointer to a three-way comparison function, as well as a parameter that specifies the size of its individual input objects. The C standard requires the comparison function to implement a total order on the items in the input array.",
  "body": "is a C standard library function that implements a sorting algorithm for arrays of arbitrary objects according to a user-provided comparison function. It is named after the \"quicker sort\" algorithm (a quicksort variant due to R. S. Scowen), which was originally used to implement it in the Unix C library, although the C standard does not require it to implement quicksort. It comes from (or in C++ Standard Library). The ability to operate on different kinds of data (polymorphism) is achieved by taking a function pointer to a three-way comparison function, as well as a parameter that specifies the size of its individual input objects. The C standard requires the comparison function to implement a total order on the items in the input array. A qsort function appears in Version 2 Unix in 1972 as a library assembly language subroutine. Its interface is unlike the modern version, in that it can be pseudo-prototyped as void qsort(void* start, void* end, unsigned int length) – sorting contiguously-stored -long byte strings from the range [ , ). This, and the lack of a replaceable comparison function, makes it unsuitable to properly sort the system's little-endian integers, or any other data structures. In Version 3 Unix, the interface is extended by calling compar(III), with an interface identical to modern-day . This function may be overridden by the user's program to implement any kind of ordering, in an equivalent fashion to the compar argument to standard (though program-global, of course). Version 4 Unix adds a C implementation, with an interface equivalent to the standard. It was rewritten in 1983 for the Berkeley Software Distribution. The function was standardized in ANSI C (1989). The assembly implementation is removed in Version 6 Unix. In 1991, Bell Labs employees observed that AT&T and BSD versions of qsort would consume quadratic time for some simple inputs. Thus Jon Bentley and Douglas McIlroy engineered a new faster and more robust implementation. McIlroy would later produce a more complex quadratic-time input, termed AntiQuicksort, in 1998. This function constructs adversarial data on-the-fly. include // Comparison function. Receives two generic (void) pointers to the items under comparison. int compareInts(const void* p, const void* q) { int x = *(const int*)p; int y = *(const int*)q; // Avoid returning x - y, which can cause undefined behaviour // because of signed integer overflow. if (x y) { // Return +1 for ascending, -1 for descending order. return 1; } else { return 0; } } // This could be more concisely written as: int compareInts(const void* p, const void* q) { int x = *(const int*)p; int y = *(const int*)q; return (x > y) - (x",
  "categories": [
    "130042203",
    "23118434",
    "23603337",
    "27152323",
    "55471069",
    "7692542"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1314080164",
  "content_hash": "b74a092d522b3e27d05fa6e87574478b18f62b69cf80ab00b02337cf63670fb1",
  "created_at": 1792316556.029857,
  "updated_at": 1759156658.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "qsort-1743478-b74a092d522b3e27",
    "type": "webpage",
    "title": "qsort",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/qsort",
    "issued": {
      "date-parts": [
        [
          2026,
          10,
          18
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          19
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:qsort-1743478-b74a092d522b3e27",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1314080164",
    "note": "Immutable snapshot qsort-1743478-b74a092d522b3e27, content root b74a092d522b3e27…"
  }
}