Java Arrays.Sort()

Ref: StackOverflow


As for Arrays.sort, Oracle implementation works as follows:

  1. For int, long, float and double there are essentially three algorithms: Insertion Sort, Dual-Pivot Stable Quicksort and Merge Sort.

1.1. If the array is large enough (currently larger than 286 elements) and it's not “almost sorted” (determined dynamically), then Merge Sort is used.

1.2. Otherwise, if the array is very small (currently less than 47 elements), then Insertion Sort is used.

1.3. Otherwise (if the array is not that small, but either smaller than 286 elements or mostly sorted), Dual-Pivot Quicksort is used.

  1. For short and char, there are Insertion Sort, Dual-Pivot Stable Quicksort and Counting Sort.

2.1. If the array is larger than a certain threshold (currently 3200 elements), then Counting Sort is used.

2.2. Otherwise, similarly to larger types, Insertion Sort or Dual-Pivot Stable Quicksort is used (using the threshold of 47 elements).

  1. For bytes, it's like for shorts, but Counting Sort is used when there are more than 29 elements (since it doesn't require that much memory).

  2. For reference types, things are complicated.

4.1. If the java.util.Arrays.useLegacyMergeSort property is set, then some sort of legacy Merge Sort is used (surprisingly), which falls back to Insertion Sort on really small arrays (less than 7 elements).

4.2. Otherwise, TimSort is used (Tim Pieter's list sort for Python), which is something similar to Merge Sort, but for arrays of less than 32 objects no merging is performed.

The point of the above is that Java people really did their research instead of blindly implementing a random sorting algorithm, hoping that everyone will be happy with it.

In my experience, I find Arrays.sort to be extremely efficient. I can think of two reasons to implement a custom algorithm: the aforementioned case using certain data properties, and sorting data that comes in different “parallel” arrays that we can't merge into one array of composite objects for whatever reason (performance, or perhaps we just don't have control over the code that produced those arrays).

Comments

Post a Comment

Popular posts from this blog

SQL basic interview question

Image
Question #1) What is SQL? Structured Query Language is a database tool which is used to create and access database to support software application. Question #2) What are tables in SQL? The table is a collection of record and its information at a single view. Question #3) What are different types of statements supported by SQL? There are 3 types of SQL statements 1) DDL (Data Definition Language):  It is used to define the database structure such as tables. It includes three statements such as Create, Alter, and Drop. Some of the DDL Commands are listed below CREATE : It is used for creating the table. 1 CREATE   TABLE  table_name 2 column_name1 data_type( size ), 3 column_name2 data_type( size ), 4 column_name3 data_type( size ), ALTER:  The ALTER table is used for modifying the existing table object in the database. ALTER TABLE table_name ADD column_name datatype OR ALTER TABLE table_name DROP ...
Read more

gsutil Vs Storage Transfer Service Vs Transfer Appliance

When transferring data from an on-premiss location, use gsutil When transferring data from another cloud storage provider, use storage transfer service gsutil is a Python application that lets you access Cloud Storage from the command line. You can use gsutil to do a wide range of bucket and object management tasks, including: Creating and deleting buckets. Uploading, downloading, and deleting objects. Listing buckets and objects. Moving, copying, and renaming objects. Editing object and bucket ACLs. gsutil performs all operations, including uploads and downloads, using HTTPS and transport-layer security (TLS). For a complete list of guides to completing tasks with gsutil, see  Cloud Storage How-to Guides . Storage Transfer Service is a product that enables you to: Move or backup data to a Cloud Storage bucket either from other cloud storage providers or from your  on-premises  storage. Move data from one Cloud Storage bucket to another, so that it is available to differe...
Read more