Bug 53196 - List<>.Sort() using insertion sort does not sort all values when equality isn't checked.
Summary: List<>.Sort() using insertion sort does not sort all values when equality isn...
Status: RESOLVED FIXED
Alias: None
Product: Class Libraries
Classification: Mono
Component: mscorlib ()
Version: unspecified
Hardware: Macintosh Mac OS
: --- normal
Target Milestone: Untriaged
Assignee: Marek Safar
URL:
Depends on:
Blocks:
 
Reported: 2017-03-09 16:59 UTC by Jered
Modified: 2017-03-28 07:35 UTC (History)
3 users (show)

Tags:
Is this bug a regression?: ---
Last known good build:


Attachments
Test Project (10.52 KB, application/zip)
2017-03-16 01:29 UTC, Jon Goldberger [MSFT]
Details


Notice (2018-05-24): bugzilla.xamarin.com is now in read-only mode.

Please join us on Visual Studio Developer Community and in the Xamarin and Mono organizations on GitHub to continue tracking issues. Bugzilla will remain available for reference in read-only mode. We will continue to work on open Bugzilla bugs, copy them to the new locations as needed for follow-up, and add the new items under Related Links.

Our sincere thanks to everyone who has contributed on this bug tracker over the years. Thanks also for your understanding as we make these adjustments and improvements for the future.


Please create a new report on GitHub or Developer Community with your current version information, steps to reproduce, and relevant error messages or log files if you are hitting an issue that looks similar to this resolved bug and you do not yet see a matching new report.

Related Links:
Status:
RESOLVED FIXED

Description Jered 2017-03-09 16:59:27 UTC
When a list is sorted, the last value in the list is sorted in the wrong order when only doing a "less than" compare.

The specific function used is:
List<>.Sort( delegate( object x, object y ) );


Example:
Input: 1, 3, 5, 2, 6, 6, 6, 6, 6, 6, 6, 7, 4

Sort logic: return x < y ? -1 : 1;

Output: 1, 2, 3, 4, 5, 6, 6, 6, 6, 6, 6, 7, 6
(Note that the last value is 6, and should be 7.)

Running this same code built on .NET (in Windows) yields the expected result.

Following is example code that can be compiled on both platforms:

using System;
using System.Collections.Generic;
using System.Linq;

namespace Sort
{
	class MainClass
	{
		public static void Main(string[] args)
		{
			int[] array = new int[] { 1, 3, 5, 2, 6, 6, 6, 6, 6, 6, 6, 7, 4 };

			List<int> list = array.ToList();

			list.Sort(delegate (int x, int y)
					   {
						   return x < y ? -1 : 1;
					   });
		}
	}
}
Comment 1 Jon Goldberger [MSFT] 2017-03-16 01:29:49 UTC
Created attachment 20371 [details]
Test Project

I am able to reproduce this behavior and confirm that the behavior is different in Mono than on .NET (Windows). Attached is a simple console app using the code in the bug description.

## Steps to reproduce

1. Open the test project in Xamarin Studio
2. Deploy the console app

Expected result: Elements in list will be sorted in ascending order, i.e. you will see in console output:

> List sorted: True
> 1, 2, 3, 4, 5, 6, 6, 6, 6, 6, 6, 6, 7,

Actual result: Last two elements not sorted correctly, i.e. console output shows:

> List sorted: True
> 1, 2, 3, 4, 5, 6, 6, 6, 6, 6, 6, 7, 6,

## Notes

Running the same project in Visual Studio yields the expected result.

## Regression status:

Not a regression. Tested back to Mono 4.6.0 and got the same results. 

## Environment

=== Xamarin Studio Enterprise ===

Version 6.2 (build 1829)
Installation UUID: ceaba76c-db06-4fbd-b326-f69ea53c3e01
Runtime:
	Mono 4.8.0 (mono-4.8.0-branch/8f6d0f6) (64-bit)
	GTK+ 2.24.23 (Raleigh theme)

	Package version: 408000520

=== NuGet ===

Version: 3.5.0.0

=== Xamarin.Profiler ===

'/Applications/Xamarin Profiler.app' not found

=== Apple Developer Tools ===

Xcode 8.2.1 (11766.1)
Build 8C1002

=== Xamarin.iOS ===

Version: 10.4.0.128 (Visual Studio Enterprise)
Hash: ba11e48
Branch: cycle9
Build date: 2017-03-10 08:48:04-0500

=== Xamarin.Android ===

Version: 7.1.0.43 (Visual Studio Enterprise)
Android SDK: /Users/jongoldberger/Library/Developer/Xamarin/android-sdk-macosx
	Supported Android versions:
		4.0.3 (API level 15)
		4.1   (API level 16)
		4.2   (API level 17)
		4.3   (API level 18)
		4.4   (API level 19)
		5.0   (API level 21)
		5.1   (API level 22)
		6.0   (API level 23)
		7.0   (API level 24)

SDK Tools Version: 25.2.5
SDK Platform Tools Version: 25.0.3
SDK Build Tools Version: 25.0.2

Java SDK: /usr
java version "1.8.0_91"
Java(TM) SE Runtime Environment (build 1.8.0_91-b14)
Java HotSpot(TM) 64-Bit Server VM (build 25.91-b14, mixed mode)

Android Designer EPL code available here:
https://github.com/xamarin/AndroidDesigner.EPL

=== Xamarin Android Player ===

Version: 0.6.5
Location: /Applications/Xamarin Android Player.app

=== Xamarin.Mac ===

Version: 3.0.0.398 (Visual Studio Enterprise)

=== Xamarin Inspector ===

Version: 1.1.2.0
Hash: cdc01b9
Branch: 1.1-release
Build date: Wed, 22 Feb 2017 23:24:11 GMT

=== Build Information ===

Release ID: 602001829
Git revision: 3a28108feb03a6384702c96ffc8c548121cdf37c
Build date: 2017-03-12 06:55:23-04
Xamarin addins: 295d27f8dcdde049a1807a76c888fc0a6557357d
Build lane: monodevelop-lion-cycle9

=== Operating System ===

Mac OS X 10.12.3
Darwin Jons-MacBook-Pro.local 16.4.0 Darwin Kernel Version 16.4.0
    Thu Dec 22 22:53:21 PST 2016
    root:xnu-3789.41.3~3/RELEASE_X86_64 x86_64

=== Enabled user installed addins ===

Addin Maker 1.3.2
Manifest.addin 0.0.0.0
Comment 3 Marek Safar 2017-03-28 07:35:45 UTC
Fixed in master