From owner-freebsd-current@freebsd.org Mon Apr 18 13:25:41 2016 Return-Path: Delivered-To: freebsd-current@mailman.ysv.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:1900:2254:206a::19:1]) by mailman.ysv.freebsd.org (Postfix) with ESMTP id CF1FDB13A83 for ; Mon, 18 Apr 2016 13:25:41 +0000 (UTC) (envelope-from rysto32@gmail.com) Received: from mail-io0-x230.google.com (mail-io0-x230.google.com [IPv6:2607:f8b0:4001:c06::230]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (Client CN "smtp.gmail.com", Issuer "Google Internet Authority G2" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 9AAB0135B for ; Mon, 18 Apr 2016 13:25:41 +0000 (UTC) (envelope-from rysto32@gmail.com) Received: by mail-io0-x230.google.com with SMTP id g185so194299083ioa.2 for ; Mon, 18 Apr 2016 06:25:41 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc; bh=ody5dmvZ3KG20f/KvlmYiirtNa4+vg089xBJ+eJrhCE=; b=sJsbZGqzASKnZW1FrHAv3EjvNFvwI53FXP2cx4+qKyWvLWX5xwsALLxjXE/ZMG87hs T2rbIeygOb6GD1TmDqD02Orw4pBiDo0Dnfgv+xWSGYK+ZRGMs91Nnik19ANc0tagVWFZ xp9GUYVQ770mnLnd6KSlnm1H5DznhA/PCRyzgjPB41Vx8GVoMGrchuhq7t1my3rhYvFL 5RmNNnz+Y6s/JjVqLKVPa6WMq9bSDF5YaDZSV+nOFqxXuTdQ8/1nAT9U2l97giiZUsUW HF/gKWkUgYuQWhE8NqSjKgIHK4R9RQqn/ruQ6FAwThyAxCTYwX+sttaRCZJi+KDXndbv ZP5Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:date :message-id:subject:from:to:cc; bh=ody5dmvZ3KG20f/KvlmYiirtNa4+vg089xBJ+eJrhCE=; b=QD6KaXScbF6URfElr0TbY6H8ecPRpgH+9MCnAaXz5VWwdHQ/afO61EpHa1/iS3Hvev 57C+JGb/5DygAiVFvT2dsb9gxAdv2X4taIaCwYM6rElpjepmfrviKTWG6V53Yxk2oeRB jnMj8DWffuXInM5/jQQk9/WBEarmuFfOhl2JKUVPPYMPtieycRKsAdBCeMaLqN7Uk0jW KBeJ3bz9Mq+5KUUj7PvtuippNCB4a9JcBT04Jeu3qVqhccYaN2FG7XvlqoaUjd4edxdt wfmq1LwSSI0DF/ts9Qkw7ROHLxMEtoG3AZaFXURW+XCTwI2Oh9SdIb+wmpM4eq6+4JWn l7CA== X-Gm-Message-State: AOPr4FVTxMltxUaTW7TJr7j1qyvHIP1NJ9TOWsm53wm6a4qDixb3yK9iE7isRQ2OAunn13ssKvs/Ghw61gYmXA== MIME-Version: 1.0 X-Received: by 10.107.159.137 with SMTP id i131mr33986800ioe.29.1460985940988; Mon, 18 Apr 2016 06:25:40 -0700 (PDT) Received: by 10.107.133.162 with HTTP; Mon, 18 Apr 2016 06:25:40 -0700 (PDT) In-Reply-To: <5714DC98.7090208@selasky.org> References: <5714C86A.8050204@selasky.org> <20160418151639.634d571d@fujitsu> <5714DC98.7090208@selasky.org> Date: Mon, 18 Apr 2016 09:25:40 -0400 Message-ID: Subject: Re: qsort() documentation From: Ryan Stone To: Hans Petter Selasky Cc: Aleksander Alekseev , FreeBSD Current Content-Type: text/plain; charset=UTF-8 X-Content-Filtered-By: Mailman/MimeDel 2.1.21 X-BeenThere: freebsd-current@freebsd.org X-Mailman-Version: 2.1.21 Precedence: list List-Id: Discussions about the use of FreeBSD-current List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 18 Apr 2016 13:25:41 -0000 On Mon, Apr 18, 2016 at 9:09 AM, Hans Petter Selasky wrote > I think the algorithm is switching to mergesort. I'll look up the paper > and add that correctly before commit. > No, it switches to insertion sort, assuming that it's acting on an already sorted array. If that assumption is wrong you still get O(n**2) complexity.